Markov chain

The chain of Markov is a sequence of random events with a finite or countable number of outcomes, characterized by the property that, speaking loosely, with a fixed present, the future is independent of the past. Named in honor of A. A. Markov (senior).

Markov chain with discrete time

Definition

Sequence of discrete random variables called a simple Markov chain (with discrete time) if

.

Thus, in the simplest case, the conditional distribution of the subsequent state of the Markov chain depends only on the current state and does not depend on all previous states (unlike the Markov chains of higher orders).

Range of values ​​of random variables called the chain space , and the number - step number.

Transition Matrix and Homogeneous Circuits [edit]

Matrix where

is called the matrix of transition probabilities on m step and vector where

- the initial distribution of the Markov chain.

Obviously, the transition probability matrix is ​​stochastic, that is,

.

A Markov chain is said to be single -pitch if the transition probability matrix does not depend on the step number, that is,

.

Otherwise, the Markov chain is called inhomogeneous. In the following, we will assume that we are dealing with homogeneous Markov chains.

Finite-dimensional distributions and transition matrix in n steps

From the properties of conditional probability and the definition of a homogeneous Markov chain we get:

,

whence the special case of the Kolmogorov – Chapman equation follows:

,

that is, the transition probability matrix for steps of a homogeneous Markov chain -th degree of the matrix of transition probabilities for 1 step. Finally,

.

Classification of Markov Chain States

• Returnable condition;
• Markov return chain;
• Achievable condition;
• The indecomposable Markov chain;
• Periodic state;
• Periodic Markov chain;
• Absorbing state;
• Ergodic condition.

Examples

• Branching process;
• Random walk;
• In the series, 4 numbers (Numb3rs), using the Markov chain as an example, try to uncover the escape of two prisoners. Season 1, Episode 13

Markov chain with continuous time

Definition

Family of discrete random variables called a Markov chain (with continuous time) if

.

A chain of Markov with continuous time is called homogeneous if

.

The matrix of transition functions and the Kolmogorov – Chapman equation

Similar to the discrete time case, the finite-dimensional distributions of a homogeneous Markov chain with continuous time are completely determined by the initial distribution

and the matrix of transition functions ( transition probabilities )

.

The matrix of transition probabilities satisfies the Kolmogorov – Chapman equation: or

Intensity matrix and Kolmogorov differential equations

By definition, the intensity matrix or equivalently

.

From the Kolmogorov-Chapman equation, two equations follow:

• Kolmogorov direct equation

  

• Kolmogorov inverse equation

  

For both equations, the initial condition is chosen . Appropriate solution

Properties of matrices P and Q [edit]

For anyone matrix has the following properties:

1. Matrix Elements non-negative: (nonnegative probability).
2. The sum of the elements in each row equals 1: (total probability), that is, the matrix is stochastic on the right (or in rows).
3. All proper numbers matrices do not exceed 1 in absolute value: . If a then .
4. Proper number matrices corresponds to at least one non-negative left eigenvector line (equilibrium): .
5. For own number matrices all root vectors are proper, that is, the corresponding Jordan cells are trivial.

Matrix has the following properties:

1. Off-diagonal matrix elements non-negative: .
2. Diagonal Matrix Elements non-positive: .
3. The sum of the elements in each row equals 0:
4. Real part of all proper numbers matrices non-positive: . If a then
5. Proper number matrices corresponds to at least one non-negative left eigenvector line (equilibrium):
6. For own number matrices all root vectors are proper, that is, the corresponding Jordan cells are trivial.

Graph of transitions, connectivity and ergodic Markov chains

For a Markov chain with continuous time, an oriented transition graph (briefly, a transition graph) is constructed according to the following rules:

• The set of vertices of the graph coincides with the set of chain states.
• Vertices connected by oriented edge , if a (i.e. the flow rate from th state in is positive.

Topological properties of the transition graph associated with the spectral properties of the matrix . In particular, the following theorems are true for finite Markov chains:

• The following three properties of A, B, and B of a finite Markov chain are equivalent (the chains possessing them are sometimes called weakly ergodic ):

A. For any two different vertices of the transition graph there is such a vertex a graph (“common drain”) that there are oriented paths from the top to the top and from the top to the top . Note : possible case or ; in this case, the trivial (empty) path from to or from to also considered an oriented way.

B. Zero eigenvalue of the matrix nondegenerate.

B. When matrix tends to the matrix, in which all the rows coincide (and coincide, obviously, with the equilibrium distribution).

• The following five properties A, B, C, D, D of a finite Markov chain are equivalent (the chains possessing them are called ergodic ):

A. The transition graph of a chain is oriented.

B. Zero eigenvalue of the matrix is non-degenerate and corresponds to a strictly positive left eigenvector (equilibrium distribution).

B. For some matrix strictly positive (i.e. for all ).

G. For all matrix strictly positive.

D. When matrix tends to a strictly positive matrix, in which all the rows coincide (and obviously coincide with the equilibrium distribution).

Examples

Let us consider Markov chains with three states and with continuous time, corresponding to the transition graphs shown in Fig. In case (a), only the following nondiagonal elements of the intensity matrix are nonzero: in case (b) are non-zero only , and in case (c) - . The remaining elements are determined by the properties of the matrix. (the sum of the elements in each row is 0). As a result, for graphs (a), (b), (c), the intensity matrices are:

Basic kinetic equation

The basic kinetic equation describes the evolution of the probability distribution in a Markov chain with continuous time. The “basic equation” here is not an epithet, but a translation of the term English. Master equation . For a probability distribution vector string the basic kinetic equation is:

and coincides, essentially, with the direct Kolmogorov equation. In the physical literature, probability column vectors are used more often and the basic kinetic equation is written in the form that explicitly uses the law of conservation of total probability:

Where

If for the basic kinetic equation there is a positive equilibrium then it can be written in the form

Lyapunov functions for the main kinetic equation

For the basic kinetic equation, there exists a rich family of convex Lyapunov functions — monotonously varying with time distribution probability functions. Let be - convex function of one variable. For any positive probability distribution ( ) we define the function Morimoto :

.

Derivative on time if satisfies the basic kinetic equation, there is

.

The last inequality holds because of the bulge .

Examples of Morimoto Functions [edit]

• , ;

this function is the distance from the current probability distribution to the equilibrium in -norm The time shift is a contraction of the space of probability distributions in this norm. (For compression properties, see the Banach Fixed Point Theorem article.)

• , ;

this function is (minus) Kullback entropy (see Kullback – Leibler Distance). In physics, it corresponds to the free energy divided by (Where —Permanent Boltzmann, - absolute temperature):

if a (Boltzmann distribution), then

.

• , ;

This function is an analogue of the free energy for Burg entropy, widely used in signal processing:

• , ;

this is a quadratic approximation for the (minus) Kullback entropy near the equilibrium point. Up to a time-constant term, this function coincides with the (minus) Fisher entropy, which is given by the following choice,

• , ;

this is (minus) Fisher entropy.

• , ;

This is one of the analogues of free energy for the entropy of Tsallis. Tsallis entropy

serves as the basis for the statistical physics of nonextensive quantities. With it tends to the classical Boltzmann – Gibbs – Shannon entropy, and the corresponding Morimoto function to the (minus) Kullback entropy.