Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

Thanks in advance.

The problem is from here, problem #2.

share|cite|improve this question
up vote 7 down vote accepted

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   |  
                   |  / \  |  
                   | /   \ |  
                   |/     \|  
                    \     /  
                     \   /  
                      \ /  

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.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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