Ergodic Theory of Markov Chains — Mathematics Knowledge System

Overview

Ergodic theory for Markov chains studies when and how a chain converges to its stationary distribution. An ergodic chain is irreducible (any state is reachable from any other) and aperiodic (no cyclical behavior). The fundamental ergodic theorem states that time averages converge to space averages under the stationary distribution. Key results include the convergence theorem (mu_n -> pi in total variation), the law of large numbers for Markov chains, and mixing time estimates.

Intuition

A Markov chain is ergodic when 'forgetting the past' happens: no matter where you start, you eventually look like you were drawn from the stationary distribution. Irreducibility ensures you can always reach every state; aperiodicity removes oscillatory behavior. Once ergodic, the empirical time average of any function converges to its expectation under pi -- analogous to the classical law of large numbers but for dependent samples.

Formal Definition

Definition

A Markov chain on a countable state space S with transition matrix P is ergodic if it is both irreducible (for all i, j there exists n with p_{ij}^{(n)} > 0) and positive recurrent (all states have finite mean return time). For an ergodic chain there exists a unique stationary distribution pi satisfying pi = pi * P.

\text{Irreducible: } \forall i,j \in S, \exists n \ge 1 : p_{ij}^{(n)} > 0

Irreducibility

\text{Aperiodic: } \gcd\{n \ge 1 : p_{ii}^{(n)} > 0\} = 1 \text{ for some (hence all) } i

Aperiodicity

\|\mu P^n - \pi\|_{\text{TV}} \to 0 \text{ as } n \to \infty \text{ for any initial distribution } \mu

Convergence in total variation

\frac{1}{n}\sum_{k=0}^{n-1} f(X_k) \to \mathbb{E}_\pi[f] \quad \text{a.s.}

Ergodic theorem (LLN for Markov chains)

Notation

Notation	Meaning
$\pi$	Unique stationary distribution: pi = pi P
$\\|\mu - \pi\\|_{\mathrm{TV}}$	Total variation distance between distributions mu and pi
$t_{\mathrm{mix}}$	Mixing time: first n such that TV distance drops below 1/4
$m_i$	Mean return time to state i: m_i = 1/pi_i

Theorems

Theorem 1: Theorem 1 (Ergodic Theorem for Markov Chains)

\text{Let } \{X_n\} \text{ be an irreducible, positive recurrent Markov chain with stationary distribution } \pi. \text{ Then for any bounded } f : S \to \mathbb{R},\quad \frac{1}{n}\sum_{k=0}^{n-1} f(X_k) \xrightarrow{a.s.} \sum_i \pi_i f(i) = \mathbb{E}_\pi[f].

Theorem 2: Theorem 2 (Convergence Theorem)

\text{If } \{X_n\} \text{ is ergodic (irreducible + aperiodic + positive recurrent), then } \lim_{n\to\infty} p_{ij}^{(n)} = \pi_j \text{ for all } i, j. \text{ Equivalently, } \|P^n(i,\cdot) - \pi\|_{\mathrm{TV}} \to 0.

Theorem 3: Theorem 3 (Mean Return Time)

\text{For an irreducible positive recurrent chain, the mean first return time to state } i \text{ is } m_i = \mathbb{E}_i[T_i] = 1/\pi_i.

Worked Examples

1
The chain alternates between 1 and 2 deterministically. It is irreducible (each state is reachable from the other), but the period of each state is 2 (p_{11}^{(n)} > 0 only for even n).
$\gcd\{n \ge 1 : p_{11}^{(n)} > 0\} = \gcd\{2, 4, 6, \ldots\} = 2$
2
The chain is periodic (period 2), so it is NOT ergodic in the sense of aperiodic+irreducible. However, it is irreducible and positive recurrent, so the stationary distribution still exists. Solving pi = pi * P:
$\pi_1 = \pi_2, \quad \pi_1 + \pi_2 = 1 \implies \pi = \left(\tfrac{1}{2}, \tfrac{1}{2}\right)$
3
The time averages still converge by the ergodic theorem (positive recurrent + irreducible suffices for LLN), but p_{ij}^{(n)} does not converge pointwise.
$\frac{1}{n}\sum_{k=0}^{n-1} f(X_k) \to \frac{1}{2}f(1) + \frac{1}{2}f(2) \quad \text{a.s.}$

✓ Answer

Not aperiodic (period 2), so not ergodic in the full sense, but stationary distribution pi = (1/2, 1/2) exists and time averages converge.

Practice Problems

Mediumfree response

A Markov chain on {1, 2, 3} has transition matrix P = [[1/2, 1/4, 1/4], [1/3, 1/3, 1/3], [1/4, 1/4, 1/2]]. Is it ergodic? Find the stationary distribution.

Hardfree response

State the ergodic theorem for Markov chains and explain why the mean return time to state i equals 1/pi_i.

Common Mistakes

Common Mistake

Assuming irreducibility alone implies convergence to stationary distribution

Irreducibility plus positive recurrence gives existence and uniqueness of pi, and the LLN. But pointwise convergence p_{ij}^{(n)} -> pi_j also requires aperiodicity.

Common Mistake

Confusing stationary distribution with limiting distribution

Every ergodic chain has both. For periodic chains, the stationary distribution exists but p_{ij}^{(n)} does not converge pointwise (it oscillates).

Quiz

Summary

An ergodic Markov chain is irreducible, aperiodic, and positive recurrent.
Ergodic theorem: time averages of f(X_k) converge a.s. to E_pi[f].
Convergence theorem: p_{ij}^{(n)} -> pi_j for all i, j.
Mean return time to state i is m_i = 1/pi_i.
Mixing time t_mix quantifies how long until the chain is close to pi in total variation.

References

BookNorris, J. R. -- Markov Chains, Chapters 1-2
BookLevin, D., Peres, Y., Wilmer, E. -- Markov Chains and Mixing Times
WebsiteWikipedia -- Ergodic Markov chain