Markov Chains: Convergence, Mixing and Eigenvalues

A distribution that updates itself

A Markov chain is a set of states and a transition matrix P, where entry P_ij is the probability of moving from state i to state j in one step. Given any starting distribution π₀ over the states — a row vector of probabilities — the distribution one step later is just π₁ = π₀ P, and running that forward repeatedly is the entire simulation.

π_{t+1} = π_t · P                one step of the chain
π★ P = π★                      stationary distribution: a left eigenvector of P with eigenvalue 1

Why a stationary distribution exists at all

For a chain that is irreducible (every state can eventually reach every other state) and aperiodic (it doesn’t get trapped cycling through states on a fixed rhythm), the Perron–Frobenius theorem guarantees a unique stationary distribution π★ that every starting distribution converges to, regardless of where it began. That combination of irreducible and aperiodic has a name — an ergodic chain — and it is exactly the condition the weather and gambler’s-ruin presets are built to satisfy or deliberately violate.

live demo · probability mass flowing between states each step● LIVE

How fast convergence actually happens

Reaching the stationary distribution isn’t instantaneous, and the speed is governed by eigenvalues of P beyond the leading one, which is always exactly 1. Sort the eigenvalues by magnitude; the second-largest, λ₂, controls how quickly the transient part of the distribution decays, shrinking roughly like |λ₂|ᵗ after t steps. The gap 1 − |λ₂| is called the spectral gap, and a larger gap means faster mixing — the chain “forgets” its starting state sooner. A chain with an eigenvalue close to 1 besides the leading one will look almost frozen for a long time before suddenly settling, which is exactly what a near-decomposable transition matrix (two weakly connected clusters of states) looks like on screen.

x_{t+1} = Pᵀ x_t / ||Pᵀ x_t||       power iteration — converges to π★ at rate |λ₂/λ₁|

Reversibility is a useful shortcut, not a requirement

Some chains satisfy detailed balance: π★_i P_ij = π★_j P_ji, meaning the probability flow from i to j exactly balances the flow back from j to i. Such chains are called reversible, and their stationary distribution can often be written down in closed form without doing any eigenvector computation at all — this is the trick behind Markov chain Monte Carlo samplers. Most real chains, including PageRank’s web-surfer model, are not reversible; they still have a perfectly well-defined stationary distribution, it simply has no shortcut formula.

Two presets, two structural differences

The PageRank preset models a web surfer randomly clicking links, with a small damping probability of jumping to any page at random — that teleportation term is not decoration, it is what guarantees the link graph (which on its own may have dead ends or disconnected clusters) becomes irreducible and aperiodic so a unique stationary distribution exists at all. Gambler’s ruin, in contrast, is not ergodic on purpose: it has two absorbing states (bankrupt or reached the target), each with a self-loop probability of 1, so probability mass drains into them over time instead of circulating forever — the interesting question there isn’t the stationary distribution, it’s the probability of ending up absorbed in one state versus the other.

Frequently asked questions

Why do some transition matrices never converge to a fixed distribution?

Convergence requires the chain to be irreducible and aperiodic. A periodic chain — one that cycles deterministically through states on a fixed schedule, like a chain that alternates strictly between two states — never settles to a single distribution; it keeps oscillating between distributions forever, even though the long-run average is well defined.

What does the spectral gap actually control?

It controls mixing speed. The gap is 1 minus the magnitude of the second-largest eigenvalue of the transition matrix; a large gap means the chain forgets its starting state within a handful of steps, while a gap near zero means convergence can take a very long time even though it's mathematically guaranteed.

What's the difference between the PageRank preset and the gambler's-ruin preset?

PageRank is built to be ergodic — its damping factor guarantees a single stationary distribution that every starting point converges to. Gambler's ruin has absorbing states on purpose, so it isn't ergodic at all; probability mass eventually gets trapped at bankruptcy or the target, and the question worth asking is which absorbing state it lands in, not what its long-run distribution looks like.

Try it live

Everything above runs in your browser — open Markov Chain and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.

▶ Open Markov Chain simulation