What is this period of this Markov chain?

676 Views Asked by At

We have the following markov matrix.

\begin{bmatrix}0&1&0\\1/2&0&1/2\\0&1&0\end{bmatrix}

So we have states 1, 2, and 3. State 2 always return to 2 in 2 steps. States 1 and 3 can return to themselves in a multiple of 2 steps. So I am assuming that the period is 2? I know the strict definition of periodicity in markov chains, but I am trying to develop an intuition for the meaning.

2

There are 2 best solutions below

0
On

(optional point) you should be able to eyeball the chain and see it is time reversible, which means it has period of 1 or 2

in general I assume a single communicating class or else discussion of periodicity isn't well defined per se

period of 2 means you draw the chain as a bipartite graph (two coloring). The natural way of viewing this is you can label the states in such a way that you start on say state 0 and only visit even numbered states on even iterations, and odd numbered states on odd iterations.

Higher order period of $t$ gets a bit uglier. From Feller vol 1, 3rd ed pages 387, 405
"The states of a Markov chain will be classified independently from two viewpoints. The classification into persistent [recurrent] and transient states is fundamental, whereas the classification into periodic and aperiodic states concerns a technical detail. It represents a nuisance in that it requires constant references to trivialities...

"In an irreducible chain with period t the states can be divided into t mutually exclusive classes... and a one-step transition always leads to a state in the right neighboring class..."

A better way of viewing periodicity comes from renewal theory:
a renewal process is called periodic if there exist integer $\lambda \gt 1$ such that renewals may occur only at $\lambda, 2\lambda, 3\lambda,...$ and the greatest $\lambda$ with this property is called the period. (p. 310)

In context of markov chains this renewal process should be viewed as starting and ending at some state $i$. The choice of $i$ is arbitrary, but periodicity is a class property so any $i$ will do.

0
On

Indeed the period of this chain is $d=2$, and the classes are $\{1, 3\}$ and $\{2 \}$. Starting from state $2$ at time $n=0$, the chain will be in state $2$ at any even time $n=2p$ with probability 1; and at odd times, the chain will belong to the set $\{1, 3\}$ with probability 1.

transition diagram

Generally speaking, for an irreducible chain, a unique partition of the state space $S$ into $d$ sets $E_0, E_1, \dots, E_{d-1}$ can be found such that, for all $k \in \{0, 1, \dots, d-1 \}$ and for any $i \in E_k$, $$\sum_{j \in E_{k+1}} p_{i,j} = 1,$$ where by convention $E_d = E_0$, and where $d$ is maximal. Therefore the chain moves from one class to the other at each transition, and this cyclically. In other words, the transition matrix $P$ can be written with blocks as follows: $$ \begin{array}{c c} & \begin{array}{c c c c c} \, E_0 \,\,\,\,& E_1 \,& E_2 & \dots & E_{d-1} \end{array}\\ \begin{array}{c} E_0\\ E_1 \\ E_2\\ \vdots\\ E_{d-1} \end{array} & \begin{pmatrix} 0 & \mathbf{A}_0 & 0 & \cdots & 0 \\ 0 & \ddots & \mathbf{A}_1 & 0 & 0\\ \vdots & \ddots & \ddots & \ddots &0\\ 0 & & 0& 0& A_{d-2}\\ \mathbf{A}_{d-1}& 0 & \cdots & \cdots & 0 \end{pmatrix} \end{array} $$ Note that if the diagonal of the transition matrix is not zero, then the chain is acyclic, i.e. $d=1$ (The converse is not true). Moreover it can be checked that $P^d$ is block-diagonal.

In our case, the order of the states can be changed to $\{1, 3, 2\}$, so that the transition matrix $P$ has the form described above: $$ \begin{array}{c c} & \begin{array}{c c c} 1 & 3 & 2 \end{array}\\ \begin{array}{c} 1 \\ 3 \\ 2 \end{array} & \begin{pmatrix} 0 & 0 & 1 \\ 0 & 0 & 1 \\ \frac{1}{2} & \frac{1}{2} & 0 \end{pmatrix} \end{array} $$ with $E_0 = \{1, 3\}$, $E_1 = \{2\}$, $\mathbf{A_0} = \begin{pmatrix}1 \\ 1\end{pmatrix}$, $\mathbf{A_1} = \begin{pmatrix}\frac{1}{2} & \frac{1}{2}\end{pmatrix}$. Moreover, we can check that the transition matrix raised to the power $d=2$ is block-diagonal: $$P^2 = \begin{pmatrix} \frac{1}{2} & \frac{1}{2} & 0 \\ \frac{1}{2} & \frac{1}{2} & 0 \\ 0 &0 &1 \end{pmatrix}.$$