3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – John Alberto Feb 25 '16 at 1:38
  • $\begingroup$ Also, if none of the eigenvalues equal 1, what would that mean? $\endgroup$ – John Alberto Feb 25 '16 at 2:11
  • $\begingroup$ @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. $\endgroup$ – amd Feb 25 '16 at 8:09
  • $\begingroup$ This is a really awesome, beautiful answer. I couldn't find anywhere online that shows what you are showing either. Just wonderful. $\endgroup$ – John Alberto Feb 25 '16 at 22:46
  • $\begingroup$ @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. $\endgroup$ – amd Feb 26 '16 at 2:58
2
$\begingroup$

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$).

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – John Alberto Feb 25 '16 at 1:42
  • $\begingroup$ @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. $\endgroup$ – amd Feb 25 '16 at 7:29
  • $\begingroup$ Good point. OK, I understand it otherwise. I really like how you use the diagonals to check for it. $\endgroup$ – John Alberto Feb 25 '16 at 22:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.