Markov Chains & Stationary Distributions
Memoryless stochastic processes and the convergence to equilibrium.
A discrete-time Markov chain on a finite state space $S$ is a sequence $X_0, X_1, \ldots$ with the Markov property:
$$P(X_{n+1} = j \mid X_n = i, X_{n-1}, \ldots) = P(X_{n+1} = j \mid X_n = i) =: P_{ij}.$$The transition matrix $P$ is stochastic ($P_{ij} \geq 0$, $\sum_j P_{ij} = 1$). The $n$-step distribution is $\pi_n = \pi_0 P^n$.
A stationary distribution $\pi$ satisfies $\pi = \pi P$. An irreducible, aperiodic finite chain has a unique stationary distribution and
$$\pi_n \xrightarrow{n \to \infty} \pi,$$regardless of $\pi_0$ (Perron–Frobenius / Markov convergence). The rate is governed by the second-largest eigenvalue $|\lambda_2|$; the mixing time scales as $1/(1 - |\lambda_2|)$.
Detailed balance $\pi_i P_{ij} = \pi_j P_{ji}$ — when it holds, the chain is reversible. Metropolis–Hastings constructs chains with prescribed $\pi$ for MCMC sampling; Google's PageRank is the stationary distribution of a damped random walk on the web graph.