Fundamental theorem of finite Markov chains
Statement
If a Markov chain on a finite state space is irreducible and aperiodic, then there exists a unique stationary distribution with , for every state, and — every row of converges to as , 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 is row-stochastic, the all-ones vector is a right eigenvector with eigenvalue 1, so 1 is also an eigenvalue of (a matrix and its transpose share eigenvalues), and there is a corresponding left eigenvector with . Irreducibility means 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 of satisfy (this is the part periodicity would break: a periodic chain has extra eigenvalues exactly on the unit circle, such as , which never die out). Writing an arbitrary starting distribution in the eigenbasis of , the component along (eigenvalue 1) survives unchanged forever, while every other component is multiplied by at step and shrinks geometrically to zero.
Combining the two steps, converges to the eigenvalue-1 component alone, which is exactly , and since this holds for every starting distribution (including each point mass, i.e. each row of the identity), every row of converges to as claimed.
Topics that use this theorem
Step-by-step proofs
No step-by-step proof yet for this theorem.
References
- David A. Levin, Yuval Peres, Elizabeth L. Wilmer (2017). Markov Chains and Mixing Times
- Sergey Brin, Lawrence Page (1998). The Anatomy of a Large-Scale Hypertextual Web Search Engine
- James R. Norris (1997). Markov Chains