# Thread: Classifcation of Markov States, Convergence

1. ## 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.

2. 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

3. 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
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.