# Classify the states of a markov chain

a)

P =$\begin{bmatrix} {1-2p} & 2p & {0} \cr {p} & {1-2p} & {p} \cr {0} & 2p & {1-2p} \cr \end{bmatrix}$

b)

P = $\begin{bmatrix} 0 & p & 0 & 1-p \cr 1-p & 0 & p & 0 \cr 0 & 1-p & 0 & p \cr p & 0 & 1-p & 0 \cr \end{bmatrix}$

In each case, calculate $p_n(i, j)$ and the mean recurrence times of the states (For each state j we may dene a corresponding stopping, the rst return time, as $T_j = min(n \ge 1: X_n = j)$. Then the mean recurrence time, j , of j is given by: j = $E(T_j|X_0 = j)$.

Im not sure how to approach this question since, it would be different for different values of p.

Any help would be appreciated, thanks

Ok so for p = 1/2 ive established that $s_0$ and $s_2$ are transient and $s_1$ is recurrent, but how could i show this for p other than 1/2?

-
$p$ should be strictly less $\frac{1}{2}$, since otherwise MC becomes periodic. Are you familiar with Kolmogorov forward equations? – Alex Feb 5 '13 at 17:31
@Alex Ohh yes, otherwise we get neg probs, I havent yet, we just started markov chains – bobdylan Feb 5 '13 at 17:33
for p = 1/2 ive established that s0 and s2 are transient and s1 is recurrent... Untrue. – Did Feb 5 '13 at 21:10

This is called Kolmogorov forward equations that are used to find stationary probabilities: $\pi_k=\lim_{t \to \infty} (P(X(t)=k)$: $$\pi_1=(1-2p) \pi_1 + p \pi_2\\ \pi_2=2p \pi_1 + (1-2p) \pi_2 + 2p \pi_3$$ You do not need the 3rd equation since you have a standardizing condition: $\pi_1 + \pi_2 + \pi_3 =1$. Same approach for the 2nd MC. Can you handle it from here?
In this case you have a system of linear equations $\mathbf{A} \mathbf{x} = \mathbf{b}$, which you have to solve for $\mathbf{x} = [\pi_1, \pi_2, \pi_3]$, where $\mathbf{A} =[-2p, p,0; 2p , -2p, p;1,1,1]$, $\mathbf{b}=[0,0,1]$