Markov Chains, Ergodicity & Stationary Distributions (PageRank)
Analyze stochastic transition matrices, the Perron-Frobenius theorem, and random-surfer teleportation.
A discrete-time Markov chain on state space S has the memoryless property P(X_{t+1} = j | X_t = i, ..., X_0) = P_{ij}. A probability distribution pi is a stationary distribution if pi = pi P (i.e., pi is a left eigenvector of P with eigenvalue lambda = 1).
Imagine a cloud of probability mass flowing across nodes of a directed graph at each clock tick according to outgoing edge weights. Regardless of which node the cloud starts on, in an irreducible, aperiodic chain the mass distribution converges exponentially fast to a unique equilibrium balance pi where inflow equals outflow at every node.
Markov Chains & Stationary Distributions (MarkovStationaryFlowScene)
Step-by-Step Symbolic LaTeX Derivation
Follow each algebraic transformation from first principles to computational implementation.
Spectral Gap & Geometric Mixing Rate
The second-largest eigenvalue modulus |lambda_2| < 1 governs how rapidly the Markov chain mixes to stationarity.
Why does PageRank add a teleportation term (1 - alpha)/N * 11^T to the web link transition matrix?
What is the Detailed Balance condition in MCMC?
Detailed balance requires pi_i P_{ij} = pi_j P_{ji} for all pairs (i, j), which is a sufficient condition guaranteeing that pi is a stationary distribution of P.