Periodic Markov chain

Periodic Markov chain is a term from stochastics and describes a property of a Markov chain that is important for convergence . A Markov chain is clearly periodic if, despite the randomness of the overall system, one can make exact predictions about the subset of the state set in which the system will be at a certain point in time. Aperiodicity is particularly important for the convergence behavior of Markov chains towards a stationary distribution .

definition

A Markov chain is given in discrete time and with at most a countable state space . Then there is a crowd for everyone ${\displaystyle Z}$ ${\displaystyle i\in Z}$

${\displaystyle N_{i}:=\{n|P(X_{n}=i|X_{0}=i)>0\}}$

the possible return times to the starting point. Then it is called the period of the state . Here denotes the greatest common factor . Is for everyone , so we set . If all the states of the Markov chain have one period, this is called aperiodic . If all states have the same period , the Markov chain is called periodic with period . In the case of periodic Markov chains, if the starting state is known, the current state can always be deduced from the time. ${\displaystyle d(i):=\operatorname {ggT} (N_{i})}$ ${\displaystyle i}$ ${\displaystyle \operatorname {ggT} }$ ${\displaystyle P(X_{n}=i|X_{0}=i)=0}$ ${\displaystyle n>0}$ ${\displaystyle d(i)=\infty }$ ${\displaystyle d>1}$ ${\displaystyle d}$

properties

• This clearly means the following: If you start in a state with a period , the system can at most return to the points in time . ${\displaystyle d(i)>1}$ ${\displaystyle nd(i)}$
• In fact, for every state with a period , a return to any period is possible from a certain point in time. So there is one so that for everyone ${\displaystyle i}$ ${\displaystyle d(i)}$ ${\displaystyle N(i)}$ ${\displaystyle p_{ii}^{nd(i)}>0}$ ${\displaystyle n>N(i)}$
• Together communicating states have the same period.
• Accordingly, in an irreducible Markov chain, all states have the same period. The chain is therefore always periodic or aperiodic.
• If the state space of the Markov chain is finite and there is a power of the transition matrix whose entries are all positive, then the Markov chain is irreducible and aperiodic.
• An irreducible, positively recurrent Markov chain is aperiodic if and only if it converges to a stationary distribution .
• In the case of an irreducible Markov chain with period d , the state space can be disjointly decomposed into

${\displaystyle Z={\dot {\bigcup _{k=0,\dots ,d-1}}}Z_{k}}$

so that when in and applies, it must apply. The decompositions can therefore only be carried out in a certain order. The decomposition thus defines a d-partite graph on the transition graph . ${\displaystyle i}$ ${\displaystyle Z_{k}}$ ${\displaystyle p_{ij}>0}$ ${\displaystyle j\in Z_{k+1\operatorname {mod} d}}$

• If the Markov chain is not irreducible, then one can consider the equivalence class of all states communicating with . This can then be broken down into disjoint subsets, as above, which can only be traversed in one direction. ${\displaystyle i}$
• If the transition graph is bipartite and connected , then the Markov chain is periodic with an even period. If it is not connected, every state has an even period. More general statements with k-partite graphs are generally not valid.

example

Finite state space

As an example, let us consider a Markov chain on state space and with a transition matrix ${\displaystyle Z=\{1,2,3,4\}}$

${\displaystyle M={\begin{pmatrix}0&1&0&0\\0&0&1&0\\0&0{,}5&0&0{,}5\\1&0&0&0\\\end{pmatrix}}}$.

Since the -step transition probabilities are exactly the diagonal entries of the -th power of the transition matrix, they are checked for positivity. It applies ${\displaystyle n}$ ${\displaystyle n}$

${\displaystyle M^{2}=0{,}5\cdot {\begin{pmatrix}0&0&2&0\\0&1&0&1\\1&0&1&0\\0&2&0&0\\\end{pmatrix}},\quad M^{3}=0{,}25\cdot {\begin{pmatrix}0&2&0&2\\2&0&2&0\\0&3&0&1\\0&0&4&0\\\end{pmatrix}},\quad M^{4}=0{,}25\cdot {\begin{pmatrix}2&0&2&0\\0&3&0&1\\1&0&3&0\\0&2&0&2\\\end{pmatrix}}.}$

The checkerboard pattern of is retained in all higher powers, only the zero and non-zero entries alternate. With that we get , and the period of state 1 is two. Since all states communicate with each other, the period of the Markov chain is also two. The disjoint decomposition of the state space is and . ${\displaystyle M^{4}}$ ${\displaystyle N_{1}=\{4,6,8,\dotsc \}}$ ${\displaystyle Z_{0}=\{1,3\}}$ ${\displaystyle Z_{1}=\{2,4\}}$

Countable state space

As an example, let us consider a homogeneous Markov chain on the state space with transition probabilities ${\displaystyle \mathbb {Z} }$

${\displaystyle P(X_{n}=k|X_{n-1}=l):={\begin{cases}1/2&{\text{falls }}\quad k=l+1\\1/2&{\text{falls }}\quad k=l-1\\0&\quad \quad \quad {\text{sonst}}\end{cases}}}$.

This can be compared to a drunk who stumbles either to the left or to the right, but always with the same probability (see Drunkard's Walk ). Then it is 0 for the state and therefore also because a return to the origin is only possible at even times. The same result applies to all other states, so the Markov chain is periodic. If a small probability were introduced at any given state of the chain to remain in the same state, the Markov chain would no longer be periodic, since z. B. applies. Any return times are then possible from the th time step. ${\displaystyle N_{0}=2\mathbb {N} }$ ${\displaystyle d(0)=2}$ ${\displaystyle l}$ ${\displaystyle N_{0}=2\mathbb {N} \cup \{2l+1+\mathbb {N} \}}$ ${\displaystyle 2l+1}$

An example of a periodic Markov chain with finite state space is the Ehrenfest model .

literature

• Ulrich Krengel : Introduction to probability theory and statistics . 8th edition, Vieweg, 2005. ISBN 978-3-834-80063-3
• Hans-Otto Georgii: Stochastics: Introduction to Probability Theory and Statistics , 4th edition, de Gruyter, 2009. ISBN 978-3-110-21526-7
• Christian Hesse: Applied probability theory : a well-founded introduction with over 500 realistic examples and tasks, Vieweg, Braunschweig / Wiesbaden 2003, ISBN 978-3-528-03183-1 .