MathLabs
TheoremProved

Fundamental theorem of finite Markov chains

Statement

If a Markov chain on a finite state space SS is irreducible and aperiodic, then there exists a unique stationary distribution π\pi with πP=π\pi P=\pi, πi>0\pi_i>0 for every state, and lim⁡n→∞Pn=1 π\lim_{n\to\infty}P^n=\mathbf 1\,\pi — every row of PnP^n converges to π\pi as n→∞n\to\infty, regardless of the starting distribution.

Why is it true?

This is the reason Markov chains are useful at all: it says the long-run behavior of a randomly evolving system settles into a single predictable pattern that forgets its starting point, and it tells us exactly what that pattern is (the unique fixed point of the transition dynamics).

Proof sketch

Existence and uniqueness. Since PP is row-stochastic, the all-ones vector is a right eigenvector with eigenvalue 1, so 1 is also an eigenvalue of PP (a matrix and its transpose share eigenvalues), and there is a corresponding left eigenvector π\pi with πP=π\pi P=\pi. Irreducibility means PP is the transition matrix of a strongly connected graph, so the Perron–Frobenius theorem applies: the eigenvalue 1 is simple (multiplicity one) and its eigenvector can be chosen strictly positive, giving uniqueness after normalizing so entries sum to 1.

Convergence. Aperiodicity plus irreducibility means all other eigenvalues λ\lambda of PP satisfy ∣λ∣<1|\lambda|<1 (this is the part periodicity would break: a periodic chain has extra eigenvalues exactly on the unit circle, such as −1-1, which never die out). Writing an arbitrary starting distribution μ0\mu_0 in the eigenbasis of PP, the component along π\pi (eigenvalue 1) survives unchanged forever, while every other component is multiplied by λn\lambda^n at step nn and shrinks geometrically to zero.

Combining the two steps, μ0Pn\mu_0 P^n converges to the eigenvalue-1 component alone, which is exactly π\pi, and since this holds for every starting distribution μ0\mu_0 (including each point mass, i.e. each row of the identity), every row of PnP^n converges to π\pi as claimed.

Topics that use this theorem

Step-by-step proofs

No step-by-step proof yet for this theorem.

References

  1. David A. Levin, Yuval Peres, Elizabeth L. Wilmer (2017). Markov Chains and Mixing Times
  2. Sergey Brin, Lawrence Page (1998). The Anatomy of a Large-Scale Hypertextual Web Search Engine
  3. James R. Norris (1997). Markov Chains