# Markov chain transition matrix

Consider the Markov chain with the following transition matrix:

$$P = \pmatrix{0& 0.5 &0 &0 &0 &0.5\\ 0.25 &0 &0.25 &0.25 &0 &0.25\\ 0 &0.5 &0 &0.5 &0 &0\\ 0 &0.25 &0.25 &0 &0.25 &0.25\\ 0 &0 &0 &0.5 &0 &0.5\\ 0.25 &0.25 &0 &0.25 &0.25 &0}$$

I'm trying to show that this chain is irreducible and aperiodic, and finding the stationary probability distribution of the chain by showing that the chain is reversible.

My attempt is to draw the state space of this, and aperiodic if gcd = 1 and irreducible if there is a path from state 1 to 2 but not vice verca.

The problem is from here, problem #2.

-

Irreducibility means that you can get from any state to any state. Here it's easy to check that we can get from state 1 to 2 to 3 to 4 to 5 to 6 to 1: the transition probabilities, in that order, are $0.5,0.25,0.5,0.25$, and $0.25$, appearing on the first superdiagonal and in the lower lefthand corner. Here's a graph of the transitions; each goes both ways, so I didn't have to worry about arrows.

                   1       3
|\     /|
| \   / |
|  \ /  |
|   2   |
|  / \  |
| /   \ |
|/     \|
6-------4
\     /
\   /
\ /
5


From it you can easily check that no matter where you start, you can return to that state in either $2$ or $3$ steps; since $\gcd(2,3)=1$, the chain is aperiodic.

To show that the chain is reversible, you must find a probability distribution $$\pi=\langle\pi_1,\pi_2,\pi_3,\pi_4,\pi_5,\pi_6\rangle$$ such that $\pi_ip_{ij}=\pi_jp_{ji}$ for $1\le i,j\le 6$. Clearly the equations with $i=j$ are satisfied no matter what $\pi_i$ is, so we can ignore them. We can also ignore any pair for which $p_{ij}=p_{ji}=0$, since $0=0$ gives no information about $\pi$. That leaves the following system of equations:

$$\begin{array}{} 0.5\pi_1=0.25\pi_2&&0.5\pi_1=0.25\pi_6\\ 0.25\pi_2=0.5\pi_3&&0.25\pi_2=0.25\pi_4&&0.25\pi_2=0.25\pi_6\\ 0.5\pi_3=0.25\pi_4\\ 0.25\pi_4=0.5\pi_5&&0.25\pi_4=0.25\pi_6\\ 0.5\pi_5=0.25\pi_6 \end{array}$$

After the fractions are cleared, we have this system:

$$\begin{array}{} 2\pi_1=\pi_2&&2\pi_1=\pi_6\\ \pi_2=2\pi_3&&\pi_2=\pi_4&&\pi_2=\pi_6\\ 2\pi_3=\pi_4\\ \pi_4=2\pi_5&&\pi_4=\pi_6\\ 2\pi_5=\pi_6 \end{array}$$

Clearly $\pi_2=\pi_4=\pi_6=2\pi_1=2\pi_3=2\pi_5$. Finally, we know that $\sum_{i=1}^6\pi_i=1$, so $$1=\sum_{i=1}^6\pi_i=3\pi_1+3\pi_2=9\pi_2\;,$$ and therefore $$\pi_1=\pi_3=\pi_5=\frac19\text{ and }\pi_2=\pi_4=\pi_6=\frac29\;.$$ In other words, the distribution $$\pi=\frac19\langle 1,2,1,2,1,2\rangle$$ satisfies the detailed balance condition and is therefore reversible. Of course this distribution is stationary.

-
To prove the reversibility, one can also note that this is the random walk on the electric network where every existing nonoriented edge has conductance 1. A bonus of this approach is then that every measure which assigns to each vertex a weight proportional to the sum of the conductances of the edges adjacent to it, is stationary. Since there are 2 edges adjacent to vertices 1, 3, 5, and 4 edges adjacent to vertices 2, 4, 6, this confirms your formula, with no computation. –  Did May 5 '12 at 5:57