Classification of States and Stationary Distributions in Markov Chains

Understand Classification of States and Stationary Distributions

Key rules to remember

Stationary distribution equations

π = πP, that is π_j = Σ_i π_i p_ij, with Σ_j π_j = 1 and π_j ≥ 0

One balance equation is redundant, so drop one and use Σπ = 1 instead.

Period of a state

d(i) = gcd{ n ≥ 1 : p_ii(n) > 0 }

If d(i) = 1 the state is aperiodic. Any state with p_ii > 0 is aperiodic.

Communication

i ↔ j if i → j and j → i

Communicating classes partition the state space.

Recurrence and transience

Recurrent: P(return to i | start at i) = 1. Transient: P(return) < 1

In a finite chain, closed class means recurrent. A class that is not closed is transient.

Mean recurrence time

m_i = 1 ÷ π_i

Applies to an irreducible chain with a stationary distribution. It is the expected number of steps to return to i. A recurrent state is positive recurrent if this expected return time is finite. In a finite chain every recurrent state is positive recurrent.

Convergence condition

Finite, irreducible and aperiodic ⇒ p_ij(n) → π_j for all i, j

Without aperiodicity the limit may not exist.

Detailed balance (check for reversibility)

π_i p_ij = π_j p_ji for all i, j

If this holds with Σπ = 1, then π is stationary. Detailed balance is sufficient but not necessary for π to be stationary; a stationary distribution need not satisfy detailed balance.

How to solve Classification of States and Stationary Distributions questions

1. 1Write the transition matrix and draw the diagram. Show only arrows where p_ij > 0.
2. 2Find the communicating classes. Check for each class whether any arrow leaves it. If none does, the class is closed.
3. 3Label each class. In a finite chain, a closed class is recurrent and a non-closed class is transient. State whether the chain is irreducible.
4. 4Find the period of each class. Look for a self-loop, or list the return lengths and take their gcd.
5. 5For a stationary distribution, write π_j = Σ π_i p_ij for each state. Drop one equation, solve in terms of one unknown, then use Σπ = 1 to normalise.
6. 6Check your answer by substituting it into one equation you did not use, and check that the probabilities sum to 1.
7. 7State the long-run result. If the chain is finite, irreducible and aperiodic, p_ij(n) → π_j. If it is periodic or reducible, say why there is no single limit.
8. 8Answer any follow-up, such as the mean return time 1 ÷ π_i or the long-run proportion of time in a state.

Quickest way: Fast route to π for a small chain

Common mistakes in Classification of States and Stationary Distributions

• Calling a class recurrent just because it is a class, or calling every state in a reducible chain recurrent.

  Students forget to check whether the class is closed.

  Fix: Look for any arrow leaving the class. If there is one, the class is transient in a finite chain.

• Claiming a chain is aperiodic because it is irreducible.

  The two properties are mixed up.

  Fix: Check the period separately. A chain that alternates between two groups of states has period 2, even though it is irreducible.

• Saying a stationary distribution exists, so p_ij(n) must converge to it.

  Stationary and limiting distributions are treated as the same thing.

  Fix: Convergence needs aperiodicity as well as irreducibility. A periodic chain has π but its n-step probabilities keep cycling.

• Solving π = πP using columns instead of rows, or using Pπ.

  The vector is treated as a column.

  Fix: Treat π as a row vector. The equation for π_j uses column j of P: π_j = Σ_i π_i p_ij.

• Forgetting to normalise, so the answer does not sum to 1.

  The balance equations only give ratios.

  Fix: Always finish with Σπ = 1 and check the sum.

• Finding the period from p_ii(1) alone, or taking the smallest return time instead of the gcd.

  Students stop at the first return length.

  Fix: List several return lengths, for example 2, 4, 6, and take the gcd of all of them.

Worked examples