# periodicity of a Markov chain

Let $\{{X}_{n}\}$ be a stationary (http://planetmath.org/StationaryProcess) Markov chain^{} with state space^{} $I$. Let ${P}_{ij}^{n}$ be the $n$-step transition probability that the process goes from state $i$ at time $0$ to state $j$ at time $n$:

$${P}_{ij}^{n}=P({X}_{n}=j\mid {X}_{0}=i).$$ |

Given any state $i\in I$, define the set

$$N(i):=\{n\ge 1\mid {P}_{ii}^{n}>0\}.$$ |

It is not hard to see that if $n,m\in N(i)$, then $n+m\in N(i)$. The *period* of $i$, denoted by $d(i)$, is defined as

$$d(i):=\{\begin{array}{cc}0\hfill & \text{if}N(i)=\mathrm{\varnothing},\hfill \\ \mathrm{gcd}(N(i))\hfill & \text{otherwise},\hfill \end{array}$$ |

where $\mathrm{gcd}(N(i))$ is the greatest common divisor^{} of all positive integers in $N(i)$.

A state $i\in I$ is said to be *aperiodic* if $d(i)=1$. A Markov chain is called *aperiodic* if every state is aperiodic.

Property. If states $i,j\in I$ communicate (http://planetmath.org/MarkovChainsClassStructure), then $d(i)=d(j)$.

###### Proof.

We will employ a common inequality involving the $n$-step transition probabilities:

$${P}_{ij}^{m+n}\ge {P}_{ik}^{m}{P}_{kj}^{n}$$ |

for any $i,j,k\in I$ and non-negative integers $m,n$.

Suppose first that $d(i)=0$. Since $i\leftrightarrow j$, ${P}_{ij}^{n}>0$ and ${P}_{ji}^{m}>0$ for some $n,m\ge 0$. This implies that ${P}_{ii}^{m+n}>0$, which forces $m+n=0$ or $m=n=0$, and hence $j=i$.

Next, assume $d(i)>0$, this means that $N(i)\ne \mathrm{\varnothing}$. Since $i\leftrightarrow j$, there are $r,s\ge 0$ such that ${P}_{ji}^{r}>0$ and ${P}_{ij}^{s}>0$, and so ${P}_{jj}^{r+s}>0$, showing $r+s\in N(j)$. If we pick any $n\in N$, we also have ${P}_{jj}^{r+n+s}\ge {P}_{ji}^{r}{P}_{ii}^{n}{P}_{ij}^{s}>0$, or $r+s+n\in N(j)$. But this means $d(j)$ divides both $r+s$ and $r+s+n$, and so $d(j)$ divides their difference^{}, which is $n$. Since $n$ is arbitrarily picked, $d(j)\mid d(i)$. Similarly, $d(i)\mid d(j)$. Hence $d(i)=d(j)$.
∎

Title | periodicity of a Markov chain |
---|---|

Canonical name | PeriodicityOfAMarkovChain |

Date of creation | 2013-03-22 16:24:28 |

Last modified on | 2013-03-22 16:24:28 |

Owner | CWoo (3771) |

Last modified by | CWoo (3771) |

Numerical id | 7 |

Author | CWoo (3771) |

Entry type | Definition |

Classification | msc 60J10 |

Defines | period of a state |

Defines | aperiodic state |

Defines | aperiodic Markov chain |