Irreducible Markov chain

Irreducibility is an attribute for discrete Markov chains , which simply states that the chain cannot be broken down (reduced) into several individual chains to subsets of the original state space. In addition to aperiodicity, irreducibility is one of the important properties of Markov chains, which is important for the convergence towards a stationary distribution . Since a Markov chain can always be represented by a transition graph, the equivalent term transitivity is also used. Simply put, transitivity means that there is a path from every state to every other state.

definition

Let be a (temporally homogeneous) Markov chain on the discrete state space . Then the Markov chain is called irreducible if and only if it is for all one there, so ${\displaystyle (X_{t}),\;t\in \mathbb {N} _{0}}$ ${\displaystyle S=\{s_{1},s_{2},s_{3},\ldots \}}$ ${\displaystyle s_{i},s_{j}\in S}$ ${\displaystyle n\in \mathbb {N} }$

${\displaystyle P(X_{n}=s_{i}|X_{0}=s_{j})>0}$

Every state must therefore be accessible from every other state with a positive probability.

Equivalent Definitions

Equivalent are:

1. The Markov chain is irreducible
2. It is is for all states . It is the waiting time from the start state to the first attainment of ${\displaystyle P(\tau _{ij}<\infty )>0}$ ${\displaystyle i,j}$ ${\displaystyle \tau _{ij}}$ ${\displaystyle i}$ ${\displaystyle j}$
3. All states of the state space communicate with one another .
4. Each state is of any other state from accessing ${\displaystyle i}$ ${\displaystyle j}$
5. There is only one communication class

If the state space is finite, the list can be expanded by the following points:

1. The transition graph of the Markov chain is strongly connected .
2. The transition matrix that describes the Markov chain is irreducible .

Some authors first define the irreducibility of a subset of the state space (also using the above criteria) and then call the Markov chain irreducible if the entire state space is an irreducible set.

Weak irreducibility

There is also the concept of weak irreducibility. A Markov chain is called weakly irreducible if and only if

${\displaystyle P(\tau _{ij}<\infty )+P(\tau _{ji}<\infty )>0}$applies, where is the waiting time defined above. ${\displaystyle \tau _{ij}}$

properties

A transition graph with transition matrix. The graph disintegrates, the matrix is ​​reducible

• Irreducible Markov chains are either periodic or aperiodic , since all states have the same period.
• Irreducible Markov chains do not have any absorbing states .
• Irreducible Markov chains are either transient or recurrent , since this property always occurs in all their states at the same time.
• If the state space is finite and the transition matrix of the Markov chain, then the following irreducibility criterion exists: If there exists such that it is true, then the Markov chain is irreducible and aperiodic. The greater than sign is to be understood as a component. ${\displaystyle M}$ ${\displaystyle n\in \mathbb {N} }$ ${\displaystyle M^{n}>0}$
• In the case of a finite state space, irreducibility results in positive recurrence.

Examples

Consider the on the state space through the transition matrix ${\displaystyle S=\{1,2,3,4\}}$

${\displaystyle M_{1}={\begin{pmatrix}1/2&1/2&0&0\\0&1/2&1/2&0\\0&0&1/2&1/2\\1/2&0&0&1/2\end{pmatrix}}}$

defined chain. If this chain is in state i, it jumps to i + 1 with a 50 percent probability, otherwise it stays at i (if i = 4, it jumps back to 1 with a 50 percent probability). Obviously, the chain can go from any state to any other state in three steps, so all states are linked. This Markov chain is therefore irreducible.

Another example: consider the matrix on the same state space

${\displaystyle M_{2}={\begin{pmatrix}1/2&0&1/2&0\\0&1/3&0&2/3\\1/2&0&1/2&0\\0&2/3&0&1/3\end{pmatrix}}}$.

Here you only get from state 1 to state 3, and from there only back to state 1. States 2 and 4 cannot be reached from 1 and 3, even in any number of steps, and vice versa. S is divided into the equivalence classes and . In this example, the chain can be broken down into two separate chains on the two equivalence classes and with matrices ${\displaystyle \{1,3\}}$ ${\displaystyle \{2,4\}}$

${\displaystyle {\begin{pmatrix}1/2&1/2\\1/2&1/2\\\end{pmatrix}}}$as well as disassemble. ${\displaystyle {\begin{pmatrix}1/3&2/3\\2/3&1/3\\\end{pmatrix}}}$

literature

• Albrecht Irle: Probability Theory and Statistics: Basics - Results - Applications. Teubner, Wiesbaden 2005.
• Kai Lai Chung: Markov Chains with Stationary Transition Probabilities . Springer, Berlin 1967.
• Esa Nummelin: General Irreducible Markov Chains and Non-Negative Operators . Cambridge University Press, Cambridge 2004.
• Hans-Otto Georgii: Stochastics: Introduction to Probability Theory and Statistics , 4th edition, de Gruyter, 2009. ISBN 978-3-110-21526-7
• Achim Klenke: Probability Theory . 3. Edition. Springer-Verlag, Berlin Heidelberg 2013, ISBN 978-3-642-36017-6 , doi : 10.1007 / 978-3-642-36018-3 .
• David Meintrup, Stefan Schäffler: Stochastics . Theory and applications. Springer-Verlag, Berlin Heidelberg New York 2005, ISBN 978-3-540-21676-6 , doi : 10.1007 / b137972 .

Individual evidence

1. ↑ Meintrup, Schäffler: Stochastics. 2005, p. 242.
2. ↑ Klenke: Probability Theory. 2013, p. 377.