Markov-chains – Steady-state probabilities with multiple recurrent-classes

markov chainsprobabilitystochastic-processes

The following question is from MIT-OCW, 6.041 Spring (2006), Tutorial-12, 2.b.

For the Markov chain below. Assume that the process is in state-3 immediately before the first transition. Then, Find $\pi_i$ for $i = 1, 2, …, 4$ the probability that the process is in state-$i$ after $10^{10}$ transitions or explain why these probabilities can’t be found.

transition-probability-graph

The solution here says – "If you assumed that $\pi_i$ denoted steady state probabilities, then these probabilities do not exist."

I want to know if the solution is wrong, since, I can compute the steady-state probabilities as follows:

Let $C_i$ be the recurrent-class corresponding to the recurrent state-$i$, then
$$
\begin{align}
\pi_i & = P_{steady} (state = i|absorbed = C_i)\, P(absorbed = C_i)
\end{align}
$$

Best Answer

The solution is wrong. Having been told that you start at $3$ and given this chain, the steady state distribution is $\frac{2}{5}(4/5,1/5,0,0) + \frac{3}{5}(0,0,0,1)=(8/25,2/25,0,3/5)$. This changes if you change the initial distribution (because there are two independent invariant distributions as a result of there being two recurrent classes), but that doesn't mean it simply doesn't exist.

The distribution after $10^{10}$ steps deviates from this by a tiny amount; in particular $p_3$ at this point is $2^{-10^{10}}$. The other probabilities will deviate by similar amounts. For this to work it was important that there is a self-edge from $1$ to $1$, so that the dynamics confined to $\{ 1,2 \}$ are aperiodic.

Related Question