# Determine periodicity from transition matrix?

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.

## 2 Answers

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.

• Not sure I totally got you there. You're saying that if a transition matrix has d eigenvalues of magnitude 1, then it has a period of d, correct? So doesn't that mean the period for T is 2, since it has 2 eigenvalues of magnitude 1? I must have misunderstood you or something. Also, I find that very interesting and cool. Can you explain why the number of eigenvalues that are equal to 1 correspond to the periodicity? – John Alberto Feb 25 '16 at 1:38
• Also, if none of the eigenvalues equal 1, what would that mean? – John Alberto Feb 25 '16 at 2:11
• @JohnAlberto Stochastic matrices always have $1$ as an eigenvalue. As for the other questions, see the updates to my answer. You appear to have mistaken having a repeated eigenvalue of $1$ with having as eigenvalues a complete set of roots of unity. Also, I’m only saying that it’s a necessary condition of periodicity. I’d have to think about it a bit to decide if that’s also a sufficient condition—perhaps so if the only eigenvalues are sets of roots of unity. – amd Feb 25 '16 at 8:09
• This is a really awesome, beautiful answer. I couldn't find anywhere online that shows what you are showing either. Just wonderful. – John Alberto Feb 25 '16 at 22:46
• @JohnAlberto I remember doing an exercise that guided you through the proof. It might be out there somewhere. Note that the states that correspond to the blocks $P_k$ correspond to a partition of the states into $d$ subsets $S_k$ such that all transitions from $S_k$ go to $S_{k+1}$ (and $S_d$ goes to $S_1$, of course). There’s a theorem that every periodic class can be so partitioned. – amd Feb 26 '16 at 2:58

Note that $T^2$ has only positive entries on the two blocks. This implies what you want: namely, the same happens to $T^n$ for $n\ge2$, simply by matrix multiplication. In particular, the entries on the diagonal are positive and so the Markov chain is aperiodic (since the period of each state is $1$).

• Just to be totally clear, you're saying that if the entries on the diagonal of T^n, where n is greater than or equal to 2, are positive, then T must be aperiodic. Otherwise, I'm guessing it must be periodic? – John Alberto Feb 25 '16 at 1:42
• @JohnAlberto The converse doesn’t hold. E.g., for $T=\pmatrix{1&0\\1&0}$, $T^n=T$, so the lower-right diagonal entry is always $0$, but $T$ is aperiodic. – amd Feb 25 '16 at 7:29
• Good point. OK, I understand it otherwise. I really like how you use the diagonals to check for it. – John Alberto Feb 25 '16 at 22:41