Markov Chains: Steady State and Mixing

A finite, irreducible, aperiodic Markov chain converges to a unique stationary distribution $\pi$ — the long-run fraction of time spent in each state — regardless of where it starts. The mixing time measures how fast this convergence happens. Applies to: random walks, PageRank, MCMC sampling, queueing theory, population genetics. Foundational results due to A. A. Markov (1906), Perron–Frobenius (1907–1912), and modern mixing theory (Diaconis, Aldous, Saloff-Coste, 1980s–2000s).

A Markov chain is a sequence of random states in which the probability of the next state depends only on the current state, not the full history (the Markov property). The central long-run question is: does the distribution of the chain settle down? For a broad and well-characterized class of chains, the answer is yes — the chain converges to a unique steady-state (stationary) distribution $\pi$ satisfying $\pi P=\pi$, and the rate of convergence is governed by the spectral gap of the transition matrix. The surprising fact is that this convergence is often exponentially fast yet can exhibit a sharp cutoff phenomenon: the distance to stationarity stays near its maximum for a long time, then plunges to near zero in a narrow window.

The Core Insight

A Markov chain "forgets" its starting point. The transition matrix $P$ acts repeatedly on distributions; under mild conditions all initial distributions are pulled toward a single fixed direction — the stationary vector $\pi$ — which is the left eigenvector of $P$ for eigenvalue $1$. Everything else contracts at a rate set by the second-largest eigenvalue modulus. Steady state is the fixed point; mixing time is the speed of approach.

Formal Statement

Markov Chain and Transition Matrix

A (time-homogeneous, discrete-time) Markov chain on a finite state space $S=\{1,\dots ,n\}$ is a sequence $X_0,X_1,X_2,\dots$ of $S$-valued random variables satisfying the Markov property:

The numbers $P_{ij}$ form the transition matrix $P$, which is row-stochastic:

If ${\mu }_t$ is the row vector giving the distribution of $X_t$ (so $({\mu }_t{)}_i=\mathrm{Pr}(X_t=i)$), then

Stationary Distribution

A probability row vector $\pi =({\pi }_1,\dots ,{\pi }_n)$ is a stationary (or steady-state, or invariant) distribution if

Irreducibility, Aperiodicity, Ergodicity

• Irreducible: every state is reachable from every other state, i.e. for all $i,j$ there exists $t$ with $(P^t{)}_{ij}>0$.
• Period of state $i$: $d(i)=\gcd \{t\ge 1:(P^t{)}_{ii}>0\}$. The chain is aperiodic if $d(i)=1$ for all $i$ (in an irreducible chain the period is common to all states).
• Ergodic: irreducible and aperiodic. Equivalently, $P^t$ has all strictly positive entries for some $t$ (a primitive matrix).

Fundamental Theorem of Markov Chains

Let $P$ be the transition matrix of a finite, irreducible, aperiodic (ergodic) Markov chain. Then:

1. There exists a unique stationary distribution $\pi$ with ${\pi }_i>0$ for all $i$.
2. Convergence: for every initial distribution ${\mu }_0$,

1. Ergodic / mean-return characterization: ${\pi }_i=1/{\mathbb{E}}_i[{\tau }_i^{+}]$, where ${\tau }_i^{+}=\min \{t\ge 1:X_t=i\}$ is the first return time to $i$.

Detailed Balance and Reversibility

A chain is reversible with respect to $\pi$ if it satisfies the detailed balance equations:

Reversible chains have real eigenvalues, because $P$ is self-adjoint in the inner product $⟨f,g{⟩}_{\pi }={\sum }_i{\pi }_i{f}_i{g}_i$.

Total Variation Distance and Mixing Time

The total variation distance between distributions $\mu ,\nu$ on $S$ is

Define the worst-case distance to stationarity at time $t$:

where ${\delta }_i$ is the point mass at $i$. The mixing time at threshold $\epsilon$ is

Spectral Gap Controls Mixing (Reversible Case)

Let $P$ be reversible and ergodic with eigenvalues $1={\lambda }_1>{\lambda }_2\ge \cdots \ge {\lambda }_n>-1$. Let ${\lambda }_{\star }=\max (|{\lambda }_2|,|{\lambda }_n|)$ be the second-largest eigenvalue modulus (SLEM) and define the absolute spectral gap ${\gamma }_{\star }=1-{\lambda }_{\star }$. Then

where ${\pi }_{\min }={\min }_i{\pi }_i$.

Why It Holds / Derivation

Convergence via Perron–Frobenius

Aperiodicity Is Necessary for Convergence

Consider the two-state chain that deterministically swaps states:

Andrey Andreyevich Markov | 1856–1922

A St. Petersburg mathematician and student of Pafnuty Chebyshev, Markov introduced his "chains" in 1906 to prove a law of large numbers for dependent variables, defying the prevailing belief that independence was required. In a famous 1913 application he analyzed the sequence of vowels and consonants in the first 20,000 letters of Pushkin's Eugene Onegin, computing transition frequencies — arguably the first statistical study of language as a Markov process. A committed atheist, he partly developed the theory to rebut Pavel Nekrasov's claim that the law of large numbers implied free will (and hence God). His framework became the backbone of stochastic modeling across the 20th century.

Building Intuition

Picture a particle hopping among rooms according to the row probabilities of $P$. Over a long time it visits room $i$ a fraction ${\pi }_i$ of all steps — that's the steady state, equation [6]. Now imagine releasing a whole gas of particles in any initial pattern. Each application of $P$ smears the pattern out a little; ergodicity ensures every room communicates with every other, so the pattern relaxes toward the equilibrium cloud $\pi$.

The rate of relaxation is set by how "connected" the chain is. A nearly-disconnected chain — two clusters joined by a thin bridge — has a tiny spectral gap ${\gamma }_{\star }$ and mixes slowly, because escaping one cluster is rare (a bottleneck, quantified by conductance). A well-connected chain has a large gap and mixes fast. Mixing time $\approx (1/{\gamma }_{\star })\log (1/{\pi }_{\min })$ in equation [11]: the $1/{\gamma }_{\star }$ is the relaxation time per mode, the $\log (1/{\pi }_{\min })$ is the price of having to fill in rarely-visited states.

The eeriest feature is cutoff: many natural chains stay glued to TV distance $\approx 1$ until a critical time, then collapse to $\approx 0$ in a window much shorter than the mixing time itself — like ice that stays solid then melts almost all at once.

Convergence of total-variation distance: ordinary exponential decay vs. the cutoff phenomenon. The gold curve shows a sharp drop near the cutoff time $t_\star$.

Worked Examples

Two-State Chain: Exact Steady State and Mixing

Random Walk on a Cycle: Reversibility and Slow Mixing

Common Misconceptions

Stationary ≠ Convergent ≠ Unique without conditions

Three distinct things must not be conflated:

1. Existence of $\pi$ holds for any finite chain (a fixed point of a stochastic matrix always exists, by Brouwer/Perron–Frobenius). Uniqueness requires irreducibility.
2. Convergence ${\mu }_0{P}^t\to \pi$ additionally requires aperiodicity. A periodic chain has a unique stationary distribution but $P^t$ does not converge — it cycles (see the swap chain proof above).
3. Reversibility (detailed balance) is sufficient but not necessary for $\pi$ to be stationary. Many important chains (e.g. PageRank, directed walks) are non-reversible yet still have a stationary distribution. Do not assume real eigenvalues unless the chain is reversible.

The spectral gap bound can be loose

Equation [11]'s upper bound carries a factor $\log (1/{\pi }_{\min })$. For chains where ${\pi }_{\min }$ is exponentially small (state space of size $2^n$), this $\log (1/{\pi }_{\min })=\Theta (n)$ factor can make the spectral bound off by a factor of $n$ from the true mixing time. Sharper tools — coupling, strong stationary times, log-Sobolev inequalities, and Wilson's method — are often needed.

A reducible chain with infinitely many stationary distributions

Let

Periodicity blocks convergence even when $\pi$ is unique

The directed $3$-cycle $1\to 2\to 3\to 1$ deterministically has $P^3=I$ and unique stationary $\pi =(\frac{1}{3},\frac{1}{3},\frac{1}{3})$, but ${\delta }_1{P}^t$ cycles through ${\delta }_1,{\delta }_2,{\delta }_3$ forever. The Cesàro (time) average converges to $\pi$, but the pointwise limit [5] does not exist. Eigenvalues are the three cube roots of unity, two of which sit on the unit circle.

Connections

• Perron–Frobenius Theorem is the linear-algebra engine behind existence, uniqueness, and positivity of $\pi$; the simplicity of the eigenvalue $1$ for a primitive matrix is ergodic convergence.
• Random Walks on Graphs are the canonical reversible chains; for a graph the stationary distribution is ${\pi }_i\propto \mathrm{deg}(i)$, and mixing connects to graph conductance via Cheeger's inequality $\frac{{\Phi }^2}{2}\le {\gamma }_{\star }\le 2\Phi$.
• Markov Chain Monte Carlo inverts the problem: design $P$ (e.g. Metropolis–Hastings, Gibbs sampler) so that a prescribed target $\pi$ is stationary, then run until mixed to draw samples.
• Eigenvalues and Eigenvectors provide the full decomposition: $\pi$ is the left eigenvector for $\lambda =1$; the SLEM controls speed.
• Hidden Markov Models and Continuous-Time Markov Chains generalize the framework (the latter via the generator matrix $Q$ with $\pi Q=0$).
• Coupling of Markov Chains gives an alternative, often sharper, route to mixing-time bounds: run two copies until they meet.

Real-World Applications

1. Google PageRank (Brin & Page, 1998): ranks web pages by the stationary distribution of a random surfer on the web graph, made ergodic by a "teleportation" damping factor $0.85$. The stationary vector is computed by power iteration ${\mu }_{t+1}={\mu }_{t}P$.
2. MCMC in Bayesian statistics & physics: Metropolis (1953) and Gibbs sampling draw from intractable posteriors and Boltzmann distributions; mixing time determines how long to run before samples are usable. Used in lattice QCD, protein folding, and image reconstruction.
3. Card shuffling: the Diaconis–Bayer–Shahshahani result that $7$ riffle shuffles suffice for a 52-card deck is a landmark cutoff computation ($t_{\mathrm{mix}}\approx \frac{3}{2}{\log }_{2}52$).
4. Queueing and reliability theory: birth–death chains model server queues and machine repair; $\pi$ gives long-run availability and average queue length (cf. Example 1).
5. Population genetics: the Wright–Fisher and Moran models are Markov chains on allele frequencies; fixation probabilities and equilibrium under mutation are stationary-distribution computations.
6. Speech & language: $n$-gram language models, hidden Markov models for speech recognition (Baum–Welch), and Markov text generators all rest on transition matrices.
7. Statistical mechanics / Glauber dynamics: spin systems (Ising model) relax to the Gibbs measure; the spectral gap diverges (mixing slows critically) at phase transitions — a deep link between mixing and physics.

Historical Development

• 1906 — A. A. Markov publishes the first paper on dependent chains, extending the law of large numbers beyond independence.
• 1907 — Oskar Perron proves his theorem on positive matrices (positive dominant eigenvalue).
• 1912 — Georg Frobenius extends Perron's results to irreducible/primitive nonnegative matrices — the cornerstone of steady-state theory.
• 1913 — Markov's vowel/consonant analysis of Eugene Onegin, the first empirical Markov-chain study.
• 1931–1936 — Kolmogorov and others develop the general theory of stochastic processes; the modern measure-theoretic foundation of Markov chains takes shape.
• 1953 — Metropolis, Rosenbluth, Rosenbluth, Teller & Teller publish the Metropolis algorithm; MCMC is born (later generalized by Hastings, 1970).
• 1981–1984 — Diaconis & Shahshahani pioneer representation-theoretic mixing-time bounds (random transpositions on the symmetric group), introducing the cutoff phenomenon.
• 1986 — Aldous and Diaconis formalize cutoff and strong stationary times; Sinclair–Jerrum link conductance to mixing for algorithmic applications.
• 1990s–2000s — Saloff-Coste, Diaconis, and others develop log-Sobolev and Nash inequalities for sharp mixing rates; Levin–Peres–Wilmer's textbook (2008) consolidates the field.

Subtleties & Limits

• Cutoff conjecture (Peres): it is conjectured that for "nice" families of reversible chains, cutoff occurs iff the product $t_{\mathrm{mix}}\cdot {\gamma }_{\star }\to \infty$. This is proven in several cases (e.g. birth–death chains, Ding–Lubetzky–Peres) but remains open in general.
• Sharp mixing for specific models: the exact mixing time (with constants and cutoff window) for many natural chains — certain card shuffles, the mean-field Ising/Glauber dynamics at and near criticality, random walks on random graphs — is still being pinned down.
• Non-reversible speedups: deliberately breaking detailed balance can accelerate mixing (lifting, non-reversible MCMC), but a complete theory of how much and when is incomplete.
• Infinite and continuous state spaces: existence of $\pi$ requires positive recurrence; null-recurrent and transient chains may have no stationary probability distribution. General-state-space convergence (Harris recurrence, geometric ergodicity, drift conditions à la Meyn–Tweedie) is subtler than the finite case treated here.
• Computational hardness: estimating mixing time or spectral gap of a chain given only sample access is itself a hard statistical/algorithmic problem.

See Also