How long until it forgets

The four rungs below this one establish that a finite irreducible aperiodic chain has a unique stationary distribution, that it converges to it from anywhere, that the long-run share of time in each state is that distribution, and that removing finiteness produces three different regimes.

Every one of those is a statement about the limit. None of them says anything about when the limit is reached, and for anybody actually using a chain that is the only question.

The right notion of distance #

Before “how long” can be asked, “how far” needs a definition, and the standard one is worth understanding because it is chosen rather than obvious.

The total variation distance between two distributions is half the sum of the absolute differences of their probabilities. Equivalently, and more usefully, it is the largest difference in probability the two assign to any single event:

$$\|\mu - \nu\|_{TV} = \max_{A} |\mu(A) - \nu(A)|.$$

That second reading is what makes it the right measure. A distance of $\varepsilon$ means no question whatever about the state can be answered with an advantage bigger than $\varepsilon$ by knowing which of the two distributions is in play. It is a guarantee about every event at once, not about any particular one.

The alternatives are worse in specific ways worth knowing. Comparing the two distributions state by state and taking the largest difference misses events that pool many small discrepancies. Comparing them by a squared distance weights the states equally, which is wrong when the stationary distribution is very uneven. Total variation is the measure under which a guarantee transfers to every downstream question, which is what a guarantee about a sampler has to do.

The mixing time is then the number of steps needed, from the worst possible start, to bring the distance below a threshold — conventionally a quarter, since the distance then falls geometrically and any smaller threshold costs only a constant factor more. Any threshold below a half would do; a half itself would not, since a chain can sit at exactly a half without converging.

The distance falls geometrically #

The hero figure’s straight lines are the whole phenomenon, and the reason for them is linear algebra.

The distribution after $k$ steps is the starting distribution times the $k$-th power of the transition matrix. That matrix has eigenvalue one, whose eigenvector is the stationary distribution, and every other eigenvalue is smaller than one in absolute value — which is exactly what irreducible and aperiodic buys.

Write the starting distribution as the stationary one plus a correction. The correction sums to zero — both distributions sum to one — so it has no component along the stationary direction, and it is a combination of the other eigenvectors. Applying the matrix multiplies each component by its eigenvalue, and after $k$ steps the largest surviving component has shrunk by $\lambda_2^k$ where $\lambda_2$ is the second-largest eigenvalue in absolute value.

So the distance falls like $\lambda_2^k$, and the mixing time is about $\log(1/\varepsilon) / \log(1/\lambda_2)$. The quantity $1 - |\lambda_2|$ is the spectral gap, and everything about how fast a chain forgets is in it.

Why the gap and not the eigenvalue #

The distinction is worth insisting on because the useful statements are all about the gap.

A chain with $\lambda_2 = 0.9$ has gap $0.1$ and mixes in about forty steps to a hundredth; one with $\lambda_2 = 0.99$ has gap $0.01$ and takes four hundred and sixty. The mixing time is inversely proportional to the gap when the gap is small, since $\log(1/\lambda_2) \approx 1 - \lambda_2$ there.

So “the gap is small” and “the chain is slow” are the same statement, and the practical work of the subject is bounding gaps from below.

There is a second reason to speak of the gap rather than the eigenvalue, and it is about what happens as chains grow. A family of chains of increasing size has eigenvalues all tending to one — every large chain takes many steps to cross itself — so comparing eigenvalues between sizes says nothing. Comparing gaps says how the mixing time scales with the size, which is the question a family raises and the answer a theorem gives.

That work has a geometric flavour that the algebra conceals. A chain with a small gap is one whose state space has a bottleneck: a set of states which is hard to leave, so a walk started inside it stays inside for a long time and the distribution remembers where it began.

The conductance measures the worst such bottleneck. For a set of states $S$, look at the chance of leaving $S$ in one step given that the chain is in $S$ and distributed stationarily; the conductance is the smallest such chance over all sets carrying at most half the stationary weight. A chain with conductance $\Phi$ has gap between $\Phi^2/2$ and $2\Phi$, which is Cheeger’s inequality.

The two-sided bound is what makes it a reduction rather than a hint. A combinatorial bound on the worst bottleneck gives a spectral bound within a square, and a square is a factor that changes an exponent rather than a possibility. Every large-scale mixing result in the literature is a conductance bound underneath.

That is a genuinely useful reduction: bounding a bottleneck is a combinatorial question about the transition diagram, and bounding an eigenvalue is not.

That comparison isolates what laziness costs. Adding a probability of staying put to every state cannot change where a chain settles, since the stationary distribution is unaffected; it changes only how fast, by shrinking the gap. A chain that stays put half the time has half the gap and takes twice as long.

Laziness is nonetheless standard practice, because a chain that always moves can be periodic — the ring of three states returns to its start every three steps and never converges at all — and adding a chance of standing still destroys periodicity at the cost of a factor of two. That is a cheap price for turning a chain that does not converge into one that does.

Where the number is needed #

Three settings, and the number means something different in each.

Sampling. A chain run to sample from a distribution — the Metropolis method and its relatives — must be run for at least its mixing time before its output is worth anything. Every such computation is really the question “is this long enough?”, and the honest answer requires a mixing bound. The discarded initial run has a name, burn-in, and choosing its length by eye is universal practice and is a guess.

Shuffling. A deck of cards shuffled by riffling is a chain on the fifty-two factorial orderings, and its mixing time is the number of shuffles needed before the deck is properly random. Bayer and Diaconis showed in 1992 that seven riffle shuffles suffice and six do not, which is one of the few mixing times anybody has computed exactly — and it is the reason casinos shuffle seven times.

Their result is worth a further sentence because of how the two halves were obtained. The upper bound is a coupling-style argument dressed as a formula: the number of orderings reachable by $k$ riffles is exactly countable, and comparing it to $52!$ gives the distance. The lower bound is an explicit statistic — count the rising sequences in the deck — whose distribution differs detectably from uniform after six shuffles and does not after seven. Every sharp mixing result has that shape: a coupling above and a distinguishing statistic below.

And algorithms. Approximating the permanent of a matrix, counting the proper colourings of a graph, estimating the volume of a convex body — all are done by running a chain, and all their running times are mixing times. The subject exists because those bounds are the bottleneck: the algorithm is three lines and the analysis is a paper.

The cutoff phenomenon #

There is a feature of many chains that the geometric picture misses entirely, and it is the reason the shuffling result can be so sharp.

For a small chain the distance to stationarity falls smoothly, and “the mixing time” is a fuzzy notion — twice as many steps gives a much better approximation. For many large chains it does not behave that way. The distance stays near its maximum, then falls to nearly zero within a window much shorter than the mixing time itself.

That is the cutoff phenomenon, and where it holds the chain has a sharp threshold: below it the chain is useless, above it the chain is done, and there is very little in between. The riffle shuffle has it, which is why “seven shuffles” is a meaningful answer rather than a convention.

Diaconis’s own description of it is a graph shaped like a cliff, and the picture is the right one: the distance is near one, near one, near one, and then it is near zero. Everything the geometric argument predicts is still true — the decay is eventually geometric with the right rate — and it becomes true only after the cliff, so the geometric picture describes the tail of the behaviour and not the part anybody waits through.

Whether a given family of chains has cutoff is a hard question, and finding a criterion for it is one of the open problems of the field. The obvious guess — that a large gap relative to the mixing time implies cutoff — is known to be necessary and is not sufficient.

Coupling, which is how the bounds are got #

Since eigenvalues of large chains are unavailable, the practical technique deserves stating, and it is a genuinely beautiful one.

Run two copies of the chain at once: one from the state of interest, one from the stationary distribution. Arrange their randomness so that once they occupy the same state they move together for ever. Then at any time, the two copies differ only if they have not yet met — and the second copy is stationary at every moment by construction.

So the distance to stationarity is at most the chance the two have not met. That is the coupling inequality, and it converts a question about distributions into a question about a meeting time, which is often a straightforward calculation.

The freedom is in arranging the randomness. The two copies must each individually be a correct run of the chain; how their steps are correlated is unconstrained, and choosing the coupling cleverly is where the work is. For the riffle shuffle the coupling is a matter of tracking which cards have been separated; for a random walk on a cube it is a matter of agreeing coordinate by coordinate.

A bound obtained this way is always an upper bound, since a bad coupling meets late. Getting a matching lower bound needs a different argument — usually exhibiting an event whose probability differs between the two distributions — and the two together are what pins a mixing time down.

What it costs #

The eigenvalue is not computable for a large chain. A chain on the orderings of a deck has a transition matrix with $52!$ rows — a number with sixty-eight digits — and no eigenvalue of it will ever be computed. Every practical bound is obtained by other means — coupling, conductance, comparison with a chain whose gap is known — and the eigenvalue is the definition rather than the method.

The definition uses a threshold and the threshold is a convention. Mixing time is defined at a distance of a quarter because the geometric decay makes any other threshold a constant factor away, so nothing depends on the choice — provided the decay really is geometric, which is exactly what cutoff complicates.

And a bound is often loose by a large factor. Coupling arguments regularly give bounds that are correct in their exponent and wrong by orders of magnitude in the constant. For a practitioner deciding how long to run a chain that is the difference between a computation that finishes and one that does not, and the standard response — run it and watch a diagnostic — has no guarantee attached to it at all.

Nor does mixing say the samples are independent. After the mixing time the chain’s position is close to stationary; consecutive positions remain highly correlated. Estimating a quantity to a given accuracy needs a further calculation about the correlation — the integrated autocorrelation time, which counts how many steps are worth one independent sample and can be far larger than the mixing time. A sample average’s accuracy depends on the number of effective samples, and a chain that has mixed can still be producing them slowly.

What the pictures cannot show #

Three states is not a large chain. Every figure here is a chain with two or three states, where the eigenvalue can be computed exactly and the whole distribution written down. The subject exists because of chains with astronomically many states, where nothing in these figures is available.

The gap table compares two chains and the comparison is between two numbers. What makes one chain slow is a feature of its transition structure, and the table reports the consequence without showing the cause. A picture of the cause would be a picture of a bottleneck, which needs a chain large enough to have one.

Cutoff cannot be drawn at this size. It is a phenomenon of families of chains growing in size, and it is invisible in any single small chain — where the decay is smoothly geometric, as the hero shows. Drawing it would need a sequence of chains and a rescaled axis.

The straight lines are exact and the figure could not show otherwise. With three states the correction to stationarity is a two-dimensional vector and the decay is exactly geometric after the first step, so the lines are straight by construction rather than by observation. A large chain’s decay is a mixture of many eigenvalues and is straight only asymptotically.

And the distance is a maximum over events, drawn as a number. Total variation is defined by the worst event, and which event that is changes as the chain runs. The plotted quantity is a summary of a search the figure performs and does not display.

Where the ladder goes next #

Two subjects are raised above and left unwritten. Conductance and Cheeger’s inequality, which convert the spectral question into a combinatorial one and are the tool every large-chain bound actually uses. And the cutoff phenomenon proper, which needs a family of chains rather than a single chain.

One more belongs on this ladder by subject and is written elsewhere. Metropolis and Hastings’ construction builds a chain whose stationary distribution is whatever one asks for, and it is written under the sampling anchor rather than here, because it belongs to what a chain is for rather than to how a chain behaves. Mixing is the question that construction leaves open: it says a chain exists with the right answer at infinity, and says nothing about when the answer arrives.

Sideways, the ergodic average whose convergence this rung times is the previous rung’s, the stationary distribution being an eigenvector is where the ladder starts, and the eigenvalue argument is the same one that reads a growth rate off a matrix.

Sideways: a chain that runs the same backwards is the condition that makes the spectral argument available in the first place, and where the shares have nowhere to go is what the same eigenvalues say about the long run rather than about the approach to it.

What is worth carrying away #

A theorem about a limit is not a theorem about a computation, and the gap between them is a number worth naming.

The convergence theorems say a chain reaches its stationary distribution. Nothing in them says whether that takes ten steps or ten billion, and every application depends entirely on which. The rate is the second eigenvalue, the useful form of it is the gap, and the useful bound on the gap is a statement about bottlenecks in the transition diagram.

The habit worth taking is to ask, of any convergence result, what the rate is. A proof of convergence that carries no rate is compatible with a convergence too slow to observe, and distinguishing the two is usually a separate piece of work with its own techniques.