# 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 $P^n$ does not converge, but $P^{2n}$ and $P^{2n+1}$ do converge as n approaches infinity.
• Sep 15th 2009, 06:01 AM
BrooketheChook
Quote:

Originally Posted by BrooketheChook

Show that $P^n$ does not converge, but $P^{2n}$ and $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 $i$, $P^n(i,i)=0$ when $n$ is odd, and is positive when $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 $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 $i,j$, $P^n(i,j)$ is 0 or positive depending of the parity of $n$, hence the limit, if any, would be 0.
It is however impossible that the whole matrix $P^n$ tends to 0 since the sum of the lines must stay equal to 1 at the limit. As a conclusion, $P^n$ does not converge.

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