[Math] Existence of steady state distribution for finite state Markov chains

markov chainsmarkov-processstochastic-processes

Let's assume a Markov chain has 2 recurrent classes and a transient state from which we can go to either of the recurrent classes. If one of those recurrent classes is periodic, would it effect the existence of steady state distribution of the other (aperiodic) class?

Even if both recurrent classes are aperiodic, how can we say they both converge, (but to different values)? If I start from the transient state and make the transition to one of the recurrent classes, I will never go to the other recurrent class, and in the long run, the steady state probabilities will be zero. But I just read that we can evaluate two classes separately and they can both have convergence. It makes sense to me when there is one recurrent class and some transient states, but I don't see how we can have convergence for both recurrent classes when we have two of them.

Best Answer

The recurrent classes do not affect each other. Once we get into one recurrent class, we never leave, and the structure of the other recurrent class is irrelevant.


Just take an example, say with 4 states and transition probability matrix $(P_{ij})$ given by:

$$ (P_{ij}) = \left[ \begin{array}{cccc} 0 & 1/2 & 1/2 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{array} \right] $$

State 1 is transient. State 2 forms an aperiodic recurrent class: If we get to state 2 then we always stay there. States 3 and 4 form a periodic recurrent class: If we get to state 3, we bounce around (periodically) between 3 and 4.

So:
-Given we start in state 2: We have a steady state distribution of $\pi=[0,1,0,0]$ (the limiting probabilities converge to this, and the time average fractions of time also converge to this with probability 1).

-Given we start in state 3: The limiting probabilities do not converge (they oscillate depending on even or odd slots), but the time averages converge to $p = [0,0,1/2,1/2]$ with probability 1.

-Given we start in state 1: Then the time averages will certainly converge, but they will not converge to a constant vector with probability 1. Rather, they will converge to a random vector. What they converge to will depend on the outcome of the first transition. If $p=[p_1,p_2,p_3,p_4]$ are the time averages, then given we start in state 1 we get: $$ p = \left\{ \begin{array}{ll} [0, 1, 0, 0] &\mbox{ with prob $1/2$} \\ [0, 0, 1/2, 1/2] & \mbox{ with prob $1/2$} \end{array} \right. $$


In general, for a finite state discrete time Markov chain with $K$ recurrent classes, each recurrent class $k \in \{1, \ldots, K\}$ has a unique probability distribution $\pi_k$ that satisfies $\pi_k = \pi_k P$ (where $P$ is the transition probability matrix) and such that $\pi_k$ has support only on the states of recurrence class $k$. If we start at a state in recurrence class $k$, then with probability 1 the time averages converge to $\pi_k$. If we start in a transient state, then the time averages will converge to a random vector $p$. We will eventually end up in one of the recurrent states (being the one we first visit). We can define $\theta_k$ as the probability we first visit recurrence class $k$ (defined for each $k \in \{1, \ldots, K\}$). Then $p$ is a random vector with $p = \pi_k$ with probability $\theta_k$, for $k \in \{1, \ldots, K\}$.

Related Question