Markov Chains & Ergodicity theory

A discrete-time stochastic process {X_n, n = 0, 1, 2, ...} taking values in a countable state space S is a Markov Chain if it satisfies the Markov Property: P(X_{n+1} = j | X_n = i, X_{n-1} = i_{n-1}, ..., X_0 = i_0) = P(X_{n+1} = j | X_n = i) = P_{ij} for all states and all time steps n. In words, the conditional probability distribution of the future state X_{n+1} depends only on the present state X_n, and is conditionally independent of past history X_{n-1}, ..., X_0. If P_{ij} is independent of time n, the chain is time-homogeneous.

The Chapman-Kolmogorov equations state that the n-step transition probability from state i to state j in m + n steps satisfies: P_{ij}^{(m+n)} = ∑_{k ∈ S} P_{ik}^{(m)} P_{kj}^{(n)}. In matrix notation, letting P denote the 1-step transition probability matrix, the n-step transition matrix is simply the n-th matrix power of P: P^{(n)} = P^n. For any initial distribution vector π^{(0)}, the probability distribution over states at time n is given by π^{(n)} = π^{(0)} P^n.

A probability distribution vector π on state space S (satisfying π_i ≥ 0 and ∑ π_i = 1) is a stationary (invariant or equilibrium) distribution of Markov chain P if: π = π P. In scalar form: π_j = ∑_{i ∈ S} π_i P_{ij} for all j ∈ S. This means that if the system is initialized according to π, its distribution remains π for all future times. Mathematically, π is a normalized left eigenvector of the transition matrix P associated with the dominant eigenvalue λ_1 = 1.

By the Perron-Frobenius theorem applied to stochastic matrices: (1) The largest eigenvalue of P is exactly λ_1 = 1, and its geometric and algebraic multiplicity is 1 if the chain is irreducible; (2) The corresponding left eigenvector has strictly positive entries (π_i > 0 for all i); (3) All other eigenvalues satisfy |λ_j| ≤ 1. If the chain is also aperiodic, all non-trivial eigenvalues lie strictly inside the unit circle: |λ_j| < 1 for all j ≥ 2. Consequently, lim_{n → ∞} P^n = 1 π^T, meaning every row of P^n converges to the identical stationary vector π.

The Ergodic Theorem bridges time averages and ensemble averages. For an irreducible, positive-recurrent Markov chain, with probability 1: lim_{N → ∞} (1/N) ∑_{n=1}^N f(X_n) = ∑_{i ∈ S} f(i) π_i = E_π[f(X)]. Specifically, setting f(X) = I(X = i), the long-run fraction of time the process spends visiting state i converges almost surely to its stationary probability π_i = 1 / μ_{ii}, where μ_{ii} is the expected return time to state i. The process 'forgets' its initial starting state.

Let the eigenvalues of transition matrix P be ordered 1 = λ_1 > |λ_2| ≥ |λ_3| ≥ ···. The spectral gap is defined as γ = 1 - |λ_2|. By spectral decomposition, the distance of the n-step transition matrix from the stationary distribution decays exponentially: ||P^n - 1 π^T|| ≤ C |λ_2|^n = C exp(- n |ln |λ_2||). Thus, the mixing time required to approach equilibrium is inversely proportional to the spectral gap: t_mix ≈ 1 / γ. A small spectral gap indicates bottleneck states that slow down convergence.

A stationary Markov chain is time-reversible if the process looks statistically identical running forward or backward in time. A necessary and sufficient condition for reversibility is the Detailed Balance condition: π_i P_{ij} = π_j P_{ji} for all i, j ∈ S. The probability flux from state i to j exactly balances the reverse flux from j to i. Detailed balance implies stationarity (summing over i recovers π_j = ∑ π_i P_{ij}) and provides the core foundation for constructing Markov Chain Monte Carlo (MCMC) algorithms like Metropolis-Hastings.