Concept

Total variation

A distance between two probability distributions: the largest difference in the chance they give to any one event. It equals half the sum of the differences state by state, and a small distance means no question can tell the two apart well.

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

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

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 chain Mixing time Spectral gap Convergence Coupon collector Eigenvalue Hypercube Iteration Permutation Random walk Stationary distribution

All concepts