Markov chains: classification of states, stationary distributions

In one sentence

Irreducibility makes the stationary distribution unique, positive recurrence makes it exist, and aperiodicity makes it the limit — three separate conditions doing three separate jobs.

Why the exam asks it

Because those three get compressed into "nice chains converge", and each can fail on its own with a small example. And because the classification of states is a definition-heavy area where precise statements can be tested directly.

The idea

A chain on a countable state space with transition matrix $P$, $p_{ij}=P(X_{n+1}=j\mid X_n=i)$. Chapman–Kolmogorov: $p^{(m+n)} = p^{(m)}p^{(n)}$, so $n$-step probabilities are matrix powers.

Classifying states

• Accessible: $j$ is reachable from $i$. Communicating: each reaches the other. This is an equivalence relation, and its classes partition the space.
• Irreducible: one class — everything reaches everything.
• Recurrent: return is certain, $P_i(T_i<\infty)=1$. Transient otherwise.
• Positive recurrent: recurrent and $E_i[T_i]<\infty$. Null recurrent: recurrent with infinite expected return time.
• Period $d(i)=\gcd\{n: p^{(n)}_{ii}>0\}$. Aperiodic means $d=1$.

Recurrence, positivity and period are class properties: constant within a communicating class, so on an irreducible chain they describe the whole chain.

The three conditions

A stationary distribution satisfies $\pi P=\pi$ with $\sum\pi_i=1$.

Existence needs positive recurrence. Uniqueness needs irreducibility. Convergence $p^{(n)}_{ij}\to\pi_j$ needs aperiodicity as well.

And $\pi_i = \dfrac{1}{E_i[T_i]}$ — the long-run fraction of time in a state is the reciprocal of its expected return time, which is the most useful formula in the topic.

A finite irreducible chain is automatically positive recurrent, so existence is free there and the only question is periodicity. All the interesting failures are on infinite state spaces.

Null recurrence is real. Simple symmetric random walk on $\mathbb{Z}$ returns to the origin with probability $1$ and takes infinite expected time to do it. Recurrent, not positive recurrent, and no stationary distribution exists — the walk spreads out forever. Pólya's theorem: the walk is recurrent in one and two dimensions and transient from three up, which is the memorable form.

Periodicity blocks the limit without blocking $\pi$. The two-state chain that always switches has $P=\begin{pmatrix}0&1\\1&0\end{pmatrix}$, period $2$, and stationary distribution $(\tfrac12,\tfrac12)$. But $p^{(n)}_{11}$ alternates between $1$ and $0$ forever. The stationary distribution exists and describes the long-run average, not a limit.

Computing $\pi$

Solve $\pi P=\pi$ with $\sum\pi_i=1$ — that is, a left eigenvector for eigenvalue $1$, normalised. For two states with $p_{12}=a$ and $p_{21}=b$,

$$\pi = \left(\frac{b}{a+b}, \frac{a}{a+b}\right).$$

With $a=\tfrac13$, $b=\tfrac12$: $\pi=(\tfrac35,\tfrac25)$, and the expected return time to state one is $\tfrac53$.

Detailed balance $\pi_i p_{ij}=\pi_j p_{ji}$ is sufficient for stationarity and not necessary. A chain satisfying it is reversible, and when it holds it is much the fastest route to $\pi$ — but a chain can be stationary without being reversible, and options treat the two as equivalent.

Where intuition breaks

"Every chain has a stationary distribution." Needs positive recurrence. Random walk on $\mathbb{Z}$ has none.

"Recurrent means positive recurrent." Null recurrence sits between transient and positive recurrent, and the symmetric walk on $\mathbb{Z}$ is the standard case.

"Irreducible implies convergence to $\pi$." Needs aperiodicity too. The alternating two-state chain has a $\pi$ and no limit.

"$\pi$ is the limit of $p^{(n)}$." Only in the aperiodic case. Otherwise it is the long-run average occupancy, which is what the ergodic theorem gives.

"Detailed balance is required for stationarity." Sufficient, not necessary. Non-reversible stationary chains are common.

"A finite chain can be null recurrent." Finite plus irreducible gives positive recurrence. Null recurrence needs infinitely many states.

"Random walk in three dimensions is recurrent." Transient. Pólya's dividing line is between two and three dimensions.

The exam's angle

1. Check irreducibility by drawing the graph. Communicating classes are visible immediately and determine how many stationary distributions there are.
2. Compute the period as a gcd of return lengths. A single self-loop makes a chain aperiodic.
3. Solve $\pi P=\pi$ with the normalisation — for small chains this is two equations.
4. Use $\pi_i=1/E_i[T_i]$ whenever an expected return time is wanted.
5. Try detailed balance first on chains with a nearest-neighbour structure; if it fails, fall back to the full system.

The night before

• Chapman–Kolmogorov: $n$-step probabilities are matrix powers.
• Recurrence, positivity and period are class properties.
• Existence of $\pi$ needs positive recurrence; uniqueness needs irreducibility; convergence needs aperiodicity.
• $\pi_i = 1/E_i[T_i]$.
• Finite $+$ irreducible $\Rightarrow$ positive recurrent.
• SRW on $\mathbb{Z}$: null recurrent, no $\pi$. Pólya: recurrent in $d\le2$, transient for $d\ge3$.
• Period $2$ chain: $\pi=(\tfrac12,\tfrac12)$ exists, $p^{(n)}$ never converges.
• Two states: $\pi=\left(\frac{b}{a+b},\frac{a}{a+b}\right)$.
• Detailed balance is sufficient, not necessary.