# Classifcation of Markov States, Convergence

• Sep 14th 2009, 07:11 AM
BrooketheChook
Classifcation of Markov States, Convergence
A markov chain X has the state space transition matrix P (see attached image) where q = 1-p and 0 < p < 1

Classify the states of X and give the stationary distributions.

Show that \$\displaystyle P^n \$ does not converge, but \$\displaystyle P^{2n} \$ and \$\displaystyle P^{2n+1} \$ do converge as n approaches infinity.
• Sep 15th 2009, 06:01 AM
BrooketheChook
Quote:

Originally Posted by BrooketheChook

Show that \$\displaystyle P^n \$ does not converge, but \$\displaystyle P^{2n} \$ and \$\displaystyle P^{2n+1} \$ do converge as n approaches infinity.

I have managed to classify the states and find the stationary distributions, but I really need help with the part above. I am really stuck (Crying)
• Sep 23rd 2009, 04:07 PM
Laurent
Quote:

Originally Posted by BrooketheChook
I have managed to classify the states and find the stationary distributions, but I really need help with the part above. I am really stuck (Crying)

This relates to periodicity (the period is 2). You can see that, for any state \$\displaystyle i\$, \$\displaystyle P^n(i,i)=0\$ when \$\displaystyle n\$ is odd, and is positive when \$\displaystyle n\$ is even. Indeed, the states are "on a line", and the walk needs to perform equally many steps down and up the line to go back to the initial point, hence an even number of steps.
Therefore, if \$\displaystyle P^n(i,i)\$ converges, it must be toward 0 (there is a subsequence (the odd terms) that stays at 0).
In the same way, for any \$\displaystyle i,j\$, \$\displaystyle P^n(i,j)\$ is 0 or positive depending of the parity of \$\displaystyle n\$, hence the limit, if any, would be 0.
It is however impossible that the whole matrix \$\displaystyle P^n\$ tends to 0 since the sum of the lines must stay equal to 1 at the limit. As a conclusion, \$\displaystyle P^n\$ does not converge.

On the other hand, if you compute \$\displaystyle P^2\$, you can see that it is irreducible and aperiodic, hence (theorem...) \$\displaystyle P^{2n}\$ converges. As a by-product, we get that \$\displaystyle P^{2n+1}=P^{2n} P\$ converges as well.