I have a two part question. Let's say we have a transition matrix T:
\begin{bmatrix}
0 & 0.2 & 0.8 & 0 & 0 \\
0.7 & 0 & 0.3 & 0 & 0 \\
0.6 & 0.4 & 0 & 0 & 0 \\
0 & 0 & 0 & 0.1 & 0.9 \\
0 & 0 & 0 & 0.25 & 0.75 \\
\end{bmatrix}
There are 5 states, so lets call them A through E. I want to determine if this is irreducible and aperiodic. Clearly this isnt isnt irreducible because there's no way for state A for example to reach state D. Now, for periodicity, I think T is aperiodic. I did this part by drawing out the state diagram and seeing if there's any way for a state to reach itself with a GCF bigger than 1. Here are my questions:
1) Was I right in thinking this is aperiodic?
2) Is there a way to determine periodicity just from the transition matrix? Without drawing the diagram I mean.
Any help is appreciated.
Best Answer
I believe that you can determine this by examining the eigenvalues of the transition matrix. A recurrent chain with period $d$ will have $d$ eigenvalues of magnitude $1$, equally spaced around the unit circle. I.e., it will have as eigenvalues $e^{2\pi ki/d} (0\le k<d)$.
The basic idea behind this is that if a recurrent Markov chain has period $d>1$, you can number the states so that its matrix has the block form $$\begin{bmatrix} 0 & P_1 & 0 & \cdots & 0 \\ 0 & 0 & P_2 & \cdots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & \cdots & P_{d-1} \\ P_d & 0 & 0 & \cdots & 0 \end{bmatrix}.$$ If each of the $P_k$ is simply the scalar $1$, you have a simple permutation matrix with eigenvalues equal to the $d$th roots of unity. It’s fairly straightforward to prove that the block matrix above also has the $d$th roots of unity as eigenvalues.
When you have non-communicating sets of states as you do in the matrix $T$, you can analyze each set separately. The eigenvalues for the upper-left block are $1$ and $\frac{-5\pm i}{10}$, while the eigenvalues of the lower-right block are $1$ and $-\frac3{20}$. Neither of these blocks has roots of unity (other than $1$ itself) as eigenvalues, so the chain is aperiodic.