Markov Partition
   HOME

TheInfoList



OR:

A Markov partition in
mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
is a tool used in
dynamical systems In mathematics, a dynamical system is a system in which a function describes the time dependence of a point in an ambient space. Examples include the mathematical models that describe the swinging of a clock pendulum, the flow of water in a p ...
theory, allowing the methods of
symbolic dynamics In mathematics, symbolic dynamics is the practice of modeling a topological or smooth dynamical system by a discrete space consisting of infinite sequences of abstract symbols, each of which corresponds to a state of the system, with the dynamics (e ...
to be applied to the study of
hyperbolic dynamics In dynamical systems theory, a subset Λ of a smooth manifold ''M'' is said to have a hyperbolic structure with respect to a smooth map ''f'' if its tangent bundle may be split into two invariant subbundles, one of which is contracting and th ...
. By using a Markov partition, the system can be made to resemble a discrete-time
Markov process A Markov chain or Markov process is a stochastic model describing a sequence of possible events in which the probability of each event depends only on the state attained in the previous event. Informally, this may be thought of as, "What happe ...
, with the long-term dynamical characteristics of the system represented as a
Markov shift In mathematics, subshifts of finite type are used to model dynamical systems, and in particular are the objects of study in symbolic dynamics and ergodic theory. They also describe the set of all possible sequences executed by a finite state mach ...
. The appellation 'Markov' is appropriate because the resulting dynamics of the system obeys the
Markov property In probability theory and statistics, the term Markov property refers to the memoryless property of a stochastic process. It is named after the Russian mathematician Andrey Markov. The term strong Markov property is similar to the Markov propert ...
. The Markov partition thus allows standard techniques from
symbolic dynamics In mathematics, symbolic dynamics is the practice of modeling a topological or smooth dynamical system by a discrete space consisting of infinite sequences of abstract symbols, each of which corresponds to a state of the system, with the dynamics (e ...
to be applied, including the computation of
expectation value In probability theory, the expected value (also called expectation, expectancy, mathematical expectation, mean, average, or first moment) is a generalization of the weighted average. Informally, the expected value is the arithmetic mean of a ...
s,
correlation In statistics, correlation or dependence is any statistical relationship, whether causal or not, between two random variables or bivariate data. Although in the broadest sense, "correlation" may indicate any type of association, in statistics ...
s,
topological entropy In mathematics, topology (from the Greek words , and ) is concerned with the properties of a geometric object that are preserved under continuous deformations, such as stretching, twisting, crumpling, and bending; that is, without closing h ...
, topological zeta functions,
Fredholm determinant In mathematics, the Fredholm determinant is a complex-valued function which generalizes the determinant of a finite dimensional linear operator. It is defined for bounded operators on a Hilbert space which differ from the identity operator by a ...
s and the like.


Motivation

Let (M, \varphi) be a discrete dynamical system. A basic method of studying its dynamics is to find a symbolic representation: a faithful encoding of the points of M by sequences of symbols such that the map \varphi becomes the
shift map In mathematics, and in particular functional analysis, the shift operator also known as translation operator is an operator that takes a function to its translation . In time series analysis, the shift operator is called the lag operator. Shift ...
. Suppose that M has been divided into a number of pieces E_1, E_2, \ldots, E_r which are thought to be as small and localized, with virtually no overlaps. The behavior of a point x under the iterates of \varphi can be tracked by recording, for each n, the part E_i which contains \varphi^n (x). This results in an infinite sequence on the alphabet \ which encodes the point. In general, this encoding may be imprecise (the same sequence may represent many different points) and the set of sequences which arise in this way may be difficult to describe. Under certain conditions, which are made explicit in the rigorous definition of a Markov partition, the assignment of the sequence to a point of M becomes an almost one-to-one map whose image is a symbolic dynamical system of a special kind called a
shift of finite type In mathematics, subshifts of finite type are used to model dynamical systems, and in particular are the objects of study in symbolic dynamics and ergodic theory. They also describe the set of all possible sequences executed by a finite state machine ...
. In this case, the symbolic representation is a powerful tool for investigating the properties of the dynamical system (M, \varphi).


Formal definition

A Markov partition is a
finite cover In mathematics, and more particularly in set theory, a cover (or covering) of a set X is a collection of subsets of X whose union is all of X. More formally, if C = \lbrace U_\alpha : \alpha \in A \rbrace is an indexed family of subsets U_\alpha\s ...
of the
invariant set In mathematics, an invariant is a property of a mathematical object (or a Class (set theory), class of mathematical objects) which remains unchanged after Operation (mathematics), operations or Transformation (function), transformations of a ce ...
of the manifold by a set of curvilinear rectangles \ such that * For any pair of points x,y\in E_i, that W_s(x)\cap W_u(y) \in E_i * \operatorname E_i \cap \operatorname E_j=\emptyset for i\ne j * If x\in \operatorname E_i and \varphi(x)\in \operatorname E_j, then ::\varphi\left _u(x)\cap E_i\right\supset W_u(\varphi x) \cap E_j ::\varphi\left _s(x)\cap E_i\right\subset W_s(\varphi x) \cap E_j Here, W_u(x) and W_s(x) are the unstable and
stable manifold In mathematics, and in particular the study of dynamical systems, the idea of ''stable and unstable sets'' or stable and unstable manifolds give a formal mathematical definition to the general notions embodied in the idea of an attractor or repello ...
s of ''x'', respectively, and \operatorname E_i simply denotes the interior of E_i. These last two conditions can be understood as a statement of the
Markov property In probability theory and statistics, the term Markov property refers to the memoryless property of a stochastic process. It is named after the Russian mathematician Andrey Markov. The term strong Markov property is similar to the Markov propert ...
for the symbolic dynamics; that is, the movement of a trajectory from one open cover to the next is determined only by the most recent cover, and not the history of the system. It is this property of the covering that merits the 'Markov' appellation. The resulting dynamics is that of a
Markov shift In mathematics, subshifts of finite type are used to model dynamical systems, and in particular are the objects of study in symbolic dynamics and ergodic theory. They also describe the set of all possible sequences executed by a finite state mach ...
; that this is indeed the case is due to theorems by
Yakov Sinai Yakov Grigorevich Sinai (russian: link=no, Я́ков Григо́рьевич Сина́й; born September 21, 1935) is a Russian-American mathematician known for his work on dynamical systems. He contributed to the modern metric theory of dy ...
(1968). . and Rufus Bowen (1975),Pytheas Fogg (2002), p. 208. thus putting symbolic dynamics on a firm footing. Variants of the definition are found, corresponding to conditions on the geometry of the pieces E_i.Pytheas Fogg (2002), p. 206.


Examples

Markov partitions have been constructed in several situations. *
Anosov diffeomorphism In mathematics, more particularly in the fields of dynamical systems and geometric topology, an Anosov map on a manifold ''M'' is a certain type of mapping, from ''M'' to itself, with rather clearly marked local directions of "expansion" and "cont ...
s of the
torus In geometry, a torus (plural tori, colloquially donut or doughnut) is a surface of revolution generated by revolving a circle in three-dimensional space about an axis that is coplanar with the circle. If the axis of revolution does not tou ...
. *
Dynamical billiards A dynamical billiard is a dynamical system in which a particle alternates between free motion (typically as a straight line) and specular reflections from a boundary. When the particle hits the boundary it reflects from it without loss of speed ( ...
, in which case the covering is countable. Markov partitions make
homoclinic In mathematics, a homoclinic orbit is a trajectory of a flow of a dynamical system which joins a saddle equilibrium point to itself. More precisely, a homoclinic orbit lies in the intersection of the stable manifold and the unstable manifold of ...
and
heteroclinic orbit In mathematics, in the phase portrait of a dynamical system, a heteroclinic orbit (sometimes called a heteroclinic connection) is a path in phase space which joins two different equilibrium points. If the equilibrium points at the start and end o ...
s particularly easy to describe. The system ([0,1), x \mapsto 2x\ mod\ 1) has the Markov partition E_0 = (0,1/2), E_1 = (1/2,1), and in this case the symbolic representation of a real number in [0,1) is its binary expansion. For example: x \in E_0, Tx \in E_1, T^2x \in E_1, T^3x \in E_1, T^4x \in E_0 \Rightarrow x = (0.01110...)_2. The assignment of points of [0,1) to their sequences in the Markov partition is well defined except on the dyadic rationals - morally speaking, this is because (0.01111\dots)_2 = (0.10000\dots)_2, in the same way as 1 = 0.999\dots in decimal expansions.


References

* * {{DEFAULTSORT:Markov Partition Dynamical systems Symbolic dynamics Diffeomorphisms Markov models