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
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
by sequences of symbols such that the map
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
has been divided into a number of pieces
which are thought to be as small and localized, with virtually no overlaps. The behavior of a point
under the iterates of
can be tracked by recording, for each
, the part
which contains
. 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
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
.
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
, that
*
for
* If
and
, then
::
::
Here,
and
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
simply denotes the interior of
.
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
.
[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
has the Markov partition
, and in this case the symbolic representation of a real number in
is its binary expansion. For example:
. The assignment of points of
to their sequences in the Markov partition is well defined except on the dyadic rationals - morally speaking, this is because
, in the same way as
in decimal expansions.
References
*
*
{{DEFAULTSORT:Markov Partition
Dynamical systems
Symbolic dynamics
Diffeomorphisms
Markov models