Matpic
mathematics, in pictures
Concept

Mixing time

The number of steps a Markov chain needs, from its worst starting state, to come within a fixed distance — usually a quarter — of its stationary distribution. It is what decides how long a chain must run before its output can be used.

Named by 3 essays across one field — each of them below, with the objects they name alongside it.

Also named here as spectral gap — the same set of essays touches all of them, so they are one junction rather than several.

How fast a chain forgets where it started. The total variation distance to the stationary distribution plotted logarithmically against the number of steps, for each of 3 starting states. The curves are straight lines of equal slope.

How long until it forgets

The essays before this one settle where a chain ends up and how much time it spends there, and none of them asks how long the settling takes. That question has an exact answer, it is a single number, and it is the only thing any practical use of a chain depends on.

probability · Markov chains The narrowest door in two 6-cliques joined by one edge, and the gap it pins down. two 6-cliques joined by one edge, with the vertex set of smallest conductance coloured and the 1 edges leaving it thickened. Beside it a logarithmic ruler marks half the conductance squared, the spectral gap and twice the conductance, in that order from the bottom.

The narrowest door sets the pace

How fast a chain forgets is an eigenvalue, and nobody can compute the eigenvalues of a chain worth studying. Cheeger's inequality trades the eigenvalue for a picture — the narrowest door in the state space — and pins the one between the square of the other and twice it. Both ends of that range are reached, on graphs small enough to search completely.

probability · Markov chains How far a deck of 52 is from random after each riffle shuffle. A bar chart over one to 12 riffle shuffles of the exact total variation distance from a uniformly random deck. The bars stay near one for the first few shuffles and drop sharply around 8.

The forgetting that happens all at once

A single small chain forgets its start gradually, a little more with every step. A family of large ones can do something different — stay almost perfectly informed about where it began, and then lose all of it inside a window far shorter than the wait. That cliff is the cutoff phenomenon, and it is why "seven shuffles" is an answer rather than a convention.

probability · Markov chains

Named alongside it

The objects these essays reach for when they reach for this one.

Markov chainSpectral gapEigenvalueRandom walkTotal variationConductanceConvergenceCoupon collectorEigenvectorGraphHypercubeIteration

All concepts