Markov Chains: Steady State and Mixing

⚡ Key Takeaways

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).

💡 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.

DefinitionMarkov 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:

1

\quad \Pr(X_{t+1} = j \mid X_t = i, X_{t-1}, \dots, X_0) = \Pr(X_{t+1} = j \mid X_t = i) = P_{ij}.

Derivation hint: this is the defining assumption — conditional independence of the future from the past given the present. The numbers $P_{ij}$ form the transition matrix $P$ , which is row-stochastic:

2

\quad P_{ij} \ge 0 \quad\text{and}\quad \sum_{j=1}^{n} P_{ij} = 1 \quad\text{for all } i.

Derivation hint: each row is the conditional distribution of the next state given the current state, so it sums to 1. If $\mu_t$ is the row vector giving the distribution of $X_t$ (so $(\mu_t)_i = \Pr(X_t = i)$ ), then

3

\quad \mu_{t+1} = \mu_t P, \qquad \mu_t = \mu_0 P^{t}.

Derivation hint: apply the law of total probability over the current state, then iterate.

DefinitionStationary Distribution

A probability row vector $\pi = (\pi_1, \dots, \pi_n)$ is a stationary (or steady-state, or invariant) distribution if

4

\quad \pi P = \pi, \qquad \pi_i \ge 0, \qquad \sum_{i=1}^n \pi_i = 1.

Derivation hint: $\pi$ is a fixed point of the update [3]; it is a left eigenvector of $P$ with eigenvalue $1$ , normalized to a probability vector.

DefinitionIrreducibility, 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).

TheoremFundamental 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$ ,

5

\quad \lim_{t\to\infty} \mu_0 P^{t} = \pi, \qquad \text{equivalently} \qquad \lim_{t\to\infty} (P^t)_{ij} = \pi_j \;\;\forall i.

Derivation hint: $P^t$ converges to the rank-one matrix $\mathbf{1}^\top \pi$ ; consequence of Perron–Frobenius applied to the primitive matrix $P$ . 3. 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$ .

6

\quad \pi_i = \frac{1}{\mathbb{E}_i[\tau_i^+]}.

Derivation hint: by the renewal/strong law of large numbers, the long-run fraction of time in state $i$ equals one over the average gap between visits.

DefinitionDetailed Balance and Reversibility

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

7

\quad \pi_i P_{ij} = \pi_j P_{ji} \quad \text{for all } i,j.

Derivation hint: summing over $i$ gives $\sum_i \pi_i P_{ij} = \pi_j \sum_i P_{ji} = \pi_j$ , i.e. $\pi P = \pi$ — so detailed balance implies stationarity (but not conversely). Reversible chains have real eigenvalues, because $P$ is self-adjoint in the inner product $\langle f, g\rangle_\pi = \sum_i \pi_i f_i g_i$ .

DefinitionTotal Variation Distance and Mixing Time

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

8

\quad \|\mu - \nu\|_{\mathrm{TV}} = \tfrac12 \sum_{i\in S} |\mu_i - \nu_i| = \max_{A\subseteq S} |\mu(A) - \nu(A)|.

Derivation hint: the maximizing set $A$ is $\{i : \mu_i > \nu_i\}$ ; the $\tfrac12$ accounts for equal positive and negative mass. Define the worst-case distance to stationarity at time $t$ :

9

\quad d(t) = \max_{i \in S} \|\delta_i P^{t} - \pi\|_{\mathrm{TV}},

where $\delta_i$ is the point mass at $i$ . The mixing time at threshold $\varepsilon$ is

10

\quad t_{\mathrm{mix}}(\varepsilon) = \min\{t : d(t) \le \varepsilon\}, \qquad t_{\mathrm{mix}} := t_{\mathrm{mix}}(1/4).

Derivation hint: $\tfrac14$ is conventional; submultiplicativity $d(s+t)\le 2\,d(s)\,d(t)$ lets you boost any fixed threshold to arbitrarily small $\varepsilon$ , giving $t_{\mathrm{mix}}(\varepsilon)\le \lceil \log_2 \varepsilon^{-1}\rceil\, t_{\mathrm{mix}}$ .

TheoremSpectral 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

11

\quad t_{\mathrm{relax}} := \frac{1}{\gamma_\star}, \qquad \left(\frac{1}{\gamma_\star} - 1\right)\log\frac{1}{2\varepsilon} \;\le\; t_{\mathrm{mix}}(\varepsilon) \;\le\; \frac{1}{\gamma_\star}\,\log\frac{1}{\varepsilon\,\pi_{\min}},

where $\pi_{\min} = \min_i \pi_i$ . Derivation hint: the upper bound expands $P^t$ in the orthonormal eigenbasis of the self-adjoint operator; each non-principal mode decays as $\lambda_k^t$ , and the worst-case $\chi^2$ distance is bounded by $\lambda_\star^{2t}/\pi_{\min}$ , then converted to TV via Cauchy–Schwarz. The lower bound uses the slowest-decaying eigenfunction as a test statistic.

ProofConvergence via Perron–Frobenius

Step 1 (Eigenvalue 1 exists). Since each row of $P$ sums to $1$ , the all-ones column vector $\mathbf{1}$ satisfies $P\mathbf{1} = \mathbf{1}$ . Thus $1$ is an eigenvalue (with right eigenvector $\mathbf{1}$ ), so a left eigenvector $\pi$ with $\pi P = \pi$ also exists.

Step 2 (Spectral radius is 1). For any eigenvalue $\lambda$ with right eigenvector $v$ , pick the component $|v_k|$ of largest modulus. From $(Pv)_k = \lambda v_k$ ,

|\lambda|\,|v_k| = \Big|\sum_j P_{kj} v_j\Big| \le \sum_j P_{kj}|v_j| \le |v_k|,

so $|\lambda| \le 1$ . Hence the spectral radius equals $1$ .

Step 3 (Uniqueness and positivity — Perron–Frobenius). Ergodicity means $P^m > 0$ entrywise for some $m$ (primitivity). The Perron–Frobenius theorem for primitive nonnegative matrices guarantees a simple dominant eigenvalue equal to the spectral radius ( $=1$ ) with a strictly positive eigenvector, and all other eigenvalues satisfy $|\lambda| < 1$ . The left Perron eigenvector, normalized to sum to $1$ , is the unique stationary $\pi$ , and $\pi_i > 0$ .

Step 4 (Convergence rate). Write the spectral/Jordan decomposition. The eigenvalue $1$ contributes the rank-one projector $\Pi = \mathbf{1}^\top \pi$ (since $P\mathbf 1=\mathbf1$ , $\pi P=\pi$ ). All other modes have $|\lambda|<1$ , so

P^t = \mathbf{1}^\top \pi + O\!\big(t^{\,m-1}\,\lambda_\star^{\,t}\big) \xrightarrow{t\to\infty} \mathbf{1}^\top \pi,

where the polynomial factor $t^{m-1}$ accounts for possible Jordan blocks (absent in the reversible/diagonalizable case). Therefore $\mu_0 P^t \to \mu_0 \mathbf{1}^\top \pi = (\mu_0\mathbf{1}^\top)\pi = \pi$ , since $\mu_0\mathbf{1}^\top = 1$ . $\blacksquare$

∎

ProofAperiodicity Is Necessary for Convergence

Consider the two-state chain that deterministically swaps states:

P = \begin{pmatrix} 0 & 1 \\ 1 & 0\end{pmatrix}.

It is irreducible but has period $2$ . Its eigenvalues are $1$ and $-1$ ; the second has modulus $1$ , so $P^t$ oscillates: $P^{2k} = I$ , $P^{2k+1} = P$ . Starting from $\delta_1$ , the distribution alternates $\delta_1, \delta_2, \delta_1, \dots$ and never converges, even though the unique stationary distribution $\pi = (\tfrac12, \tfrac12)$ exists (it is the time-average). Aperiodicity removes the eigenvalue $-1$ (and other roots-of-unity eigenvalues on the unit circle), restoring genuine convergence. $\blacksquare$

∎

mathematician · 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.

🧠 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.

Figure

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

.

ExampleTwo-State Chain: Exact Steady State and Mixing

Given. A machine is either Working (W) or Broken (B). Each day: $\Pr(W\to B)=\alpha=0.1$ , $\Pr(B\to W)=\beta=0.4$ .

P = \begin{pmatrix} 1-\alpha & \alpha \\ \beta & 1-\beta \end{pmatrix} = \begin{pmatrix} 0.9 & 0.1 \\ 0.4 & 0.6 \end{pmatrix}.

Step 1 — Stationary distribution. Solve $\pi P=\pi$ with $\pi_W+\pi_B=1$ . The general solution for a $2$ -state chain is

\pi_W = \frac{\beta}{\alpha+\beta}, \qquad \pi_B = \frac{\alpha}{\alpha+\beta}.

Plugging in: $\pi_W = 0.4/0.5 = 0.8$ , $\pi_B = 0.1/0.5 = 0.2$ .

Step 2 — Eigenvalues. For a $2$ -state chain, $\lambda_1=1$ and $\lambda_2 = 1-\alpha-\beta = 1-0.5 = 0.5$ . So SLEM $\lambda_\star = 0.5$ , spectral gap $\gamma_\star = 0.5$ , relaxation time $t_{\mathrm{relax}} = 1/\gamma_\star = 2$ days.

Step 3 — Exact distance to stationarity. Starting from W ( $\delta_W$ ), the closed form is

\Pr(X_t=B) = \pi_B\big(1 - \lambda_2^{\,t}\big) = 0.2(1 - 0.5^{t}),

so $d(t) = \|\delta_W P^t - \pi\|_{\mathrm{TV}} = \pi_B\,\lambda_2^t = 0.2\cdot 0.5^t.$

Step 4 — Mixing time at $\varepsilon=1/4$ : need $0.2\cdot 0.5^t \le 0.25$ , true already at $t=0$ here (this start is close); take $\varepsilon = 0.01$ : $0.2\cdot 0.5^t \le 0.01 \Rightarrow 0.5^t \le 0.05 \Rightarrow t \ge \log 0.05/\log 0.5 \approx 4.32.$

\boxed{\;\pi=(0.8,\,0.2),\quad \gamma_\star=0.5,\quad t_{\mathrm{relax}}=2\text{ days},\quad t_{\mathrm{mix}}(0.01)=5\text{ days}\;}

ExampleRandom Walk on a Cycle: Reversibility and Slow Mixing

Given. A lazy random walk on the cycle $\mathbb{Z}_n$ ( $n$ nodes in a ring). From any node: stay with prob $\tfrac12$ , move to each neighbor with prob $\tfrac14$ . Take $n = 8$ .

Step 1 — Stationary distribution. By symmetry (vertex-transitive), $\pi$ is uniform: $\pi_i = 1/n = 1/8 = 0.125.$ Check detailed balance [7]: $\pi_i P_{ij} = \tfrac18\cdot\tfrac14 = \tfrac{1}{32} = \pi_j P_{ji}$ — reversible. ✓

Step 2 — Eigenvalues. The cycle's transition operator is diagonalized by Fourier modes. The eigenvalues are

\lambda_k = \tfrac12 + \tfrac12\cos\!\Big(\frac{2\pi k}{n}\Big), \qquad k = 0,1,\dots,n-1.

For $n=8$ : $k=1$ gives $\lambda_1 = \tfrac12 + \tfrac12\cos(\pi/4) = 0.5 + 0.3536 = 0.8536.$ Laziness keeps all $\lambda_k \ge 0$ , so $\lambda_\star = 0.8536$ .

Step 3 — Spectral gap and relaxation time.

\gamma_\star = 1 - 0.8536 = 0.1464, \qquad t_{\mathrm{relax}} = 1/\gamma_\star \approx 6.83.

Step 4 — Scaling. For general $n$ , the gap is $\gamma_\star = \tfrac12\big(1-\cos(2\pi/n)\big) \approx \pi^2/n^2$ for large $n$ . So $t_{\mathrm{relax}} = \Theta(n^2)$ and the mixing time scales as

t_{\mathrm{mix}} = \Theta(n^2).

This diffusive $n^2$ scaling reflects that the walk must random-walk a distance $\sim n$ to forget its start, taking $\sim n^2$ steps.

\boxed{\;\pi_i = 1/8,\quad \lambda_\star \approx 0.854,\quad t_{\mathrm{relax}}\approx 6.8\text{ steps},\quad t_{\mathrm{mix}}=\Theta(n^2)\;}

⚠️ 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.

CounterexampleA reducible chain with infinitely many stationary distributions

Let

P = \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}

(two absorbing states, the identity matrix). It is not irreducible. Every distribution $\pi = (p, 1-p)$ satisfies $\pi P = \pi$ , so there are infinitely many stationary distributions and no convergence to a single one — the limit depends entirely on $\mu_0$ . This shows irreducibility is essential for the uniqueness clause of the Fundamental Theorem.

CounterexamplePeriodicity blocks convergence even when

\pi

is unique

The directed $3$ -cycle $1\to2\to3\to1$ deterministically has $P^3=I$ and unique stationary $\pi=(\tfrac13,\tfrac13,\tfrac13)$ , 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.

connection

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 \deg(i)$ , and mixing connects to graph conductance via Cheeger's inequality $\tfrac{\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.
<a class="wiki-link" href="/wiki/ndli-iit-kgp-ma10002-mathematics-ii-eigenvalues-and-eigenvectors">Eigenvalues and Eigenvectors</a> provide the full decomposition: $\pi$ is the left eigenvector for $\lambda=1$ ; the SLEM controls speed.
<a class="wiki-link" href="/wiki/cs-nlp-hidden-markov-models">Hidden Markov Models</a> 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.

🔬 Where this appears

⏳ History

- 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.

open-problem

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.

Markov Chains: Steady State and Mixing

Formal Statement

Why It Holds / Derivation

Building Intuition

Worked Examples

Common Misconceptions

Connections

Real-World Applications

Historical Development

Subtleties & Limits

See Also