The forgetting that happens all at once

The two essays before this one describe how a chain forgets as a slope. How long until it forgets showed the distance to stationarity falling by a constant factor every step, at a rate set by the second eigenvalue, and the narrowest door bounded that rate by a bottleneck. Both are about a single chain, and a single chain’s forgetting is gradual: twice the steps, much closer to random.

The figure below does not look like a slope. It is an ordinary deck of fifty-two cards, riffle-shuffled over and over, with the exact distance of its order from a perfectly random one after each shuffle. For four shuffles the distance is $1.00$ to two places — the deck is, for every practical purpose, still entirely determined by where it started. Then $0.92$, $0.61$, $0.33$, $0.17$, $0.09$. The deck forgets almost nothing for four shuffles and almost everything in the next four.

That shape has a name, the cutoff phenomenon, and it is not a feature any single chain can show. It belongs to families of chains growing in size, and this essay measures it on three families where the distances can be computed exactly: decks of cards, walks on cubes, and — as the control that has none — walks on rings.

Fifty-two factorial, exactly #

The distance in the hero is not simulated. A deck of $52$ has $52! \approx 8 \times 10^{67}$ orderings, and no sampling could estimate a distance over that many to three places. It is computed from a formula Dave Bayer and Persi Diaconis found in 1992.

The shuffle is the Gilbert–Shannon–Reeds model of a riffle: cut the deck at a point chosen by fair coin flips, so that the halves are usually near even, then drop cards one at a time from the bottom of either half with chance proportional to how many that half still holds. It is a model of how a competent human shuffles, and recorded human riffles fit it well.

After $k$ such shuffles, the chance of any particular ordering depends on one number only: its count of rising sequences, the maximal runs of consecutive card values that appear in increasing positions. A single riffle interleaves two packets, and so leaves at most two rising sequences; $k$ riffles leave at most $2^k$. Bayer and Diaconis showed that an ordering with $r$ rising sequences has chance exactly

$$\frac{1}{2^{kn}} \binom{2^k + n - r}{n},$$

and the number of orderings of $n$ cards with $r$ rising sequences is an Eulerian number. So the distance from uniform — half the sum, over every ordering, of the difference between its chance and $1/n!$ — is a sum of only $n$ terms, one per value of $r$. The figure evaluates it in whole-number arithmetic, with integers of several hundred digits, and checks every value against the table Bayer and Diaconis published. It also checks that the Eulerian numbers add up to exactly $52!$, which is the statement that every ordering was counted once.

A deck eight times the size needs three more doublings of the number of packets, and the cliff moves by that much and no further: $\tfrac32 \log_2 416 \approx 13$ against $8.6$. Its width barely changes. For the larger deck the distance is above $0.98$ for nine shuffles and below a quarter after twelve, which is a plateau of nine and a drop of three — longer than the smaller deck’s plateau and no wider in its drop. That is the whole of cutoff in two pictures, and the rest of this essay makes it precise.

The famous conclusion, seven shuffles, needs a word of care. At seven the distance is $0.334$, above the quarter at which mixing is conventionally declared; the quarter is crossed at eight. Bayer and Diaconis’s own argument for seven was not a threshold but the shape: before seven the distance is close to one and falling fast, after it the distance halves with each shuffle, as the geometric picture predicts. Seven is where the cliff ends and the slope begins. Under any fixed threshold the answer is seven or eight or nine; under all of them, it is close to $\tfrac32 \log_2 52 \approx 8.6$, and the reason is that the cliff is narrow.

A family, and a rescaled clock #

Cutoff is a statement about how the shape changes as the chain grows, so it needs a family whose members can all be computed exactly, including very large ones. The lazy walk on a cube is the cleanest there is.

The $n$-dimensional cube has $2^n$ corners, each a string of $n$ zeros and ones, and the lazy walk picks a coordinate at random and replaces it with a fresh random bit. The chain has $2^n$ states, far too many to handle directly for $n$ in the hundreds. But the walk started from the all-zero corner is symmetric under every reordering of the coordinates, so after any number of steps its distribution is uniform on each set of corners with the same number of 1s. The distance from uniform is then the distance between the number of 1s and a binomial distribution — a chain on $n + 1$ states. The figure checks that grouping against the full $256$-state chain at $n = 8$, step by step, before trusting it at $n = 1{,}024$.

On this clock the curves close in on a step function at one. That is the definition of cutoff: there is a time $t_n$ — here $\tfrac12 n \ln n$ — such that for any fixed $\varepsilon$, the chain is still far from random at $(1 - \varepsilon) t_n$ and close to it at $(1 + \varepsilon) t_n$, once $n$ is large enough. The time for $1{,}024$ dimensions is about $3{,}550$ steps; the walk is still at a distance above $0.9$ after $2{,}300$ steps and below $0.1$ after about $4{,}960$ — a fall that takes roughly three quarters of the time it marks.

The convergence to a step is slow, and the figure shows why. The fall from $0.9$ to $0.1$ takes $1.66$ units of the clock at $n = 16$, and still $0.74$ at $n = 1{,}024$; the width falls like $1/\ln n$, which means that to halve it the dimension must be squared. Cutoff is a limit, and at any size that can be drawn it is a steepening rather than a step.

The cliff has a width #

A step function in the limit leaves open how wide the cliff is at each size. Recentring the clock answers it.

Measured from $\tfrac12 n \ln n$ in steps of $n$, the curves coincide. The window of the cutoff is of order $n$, while its location is of order $n \ln n$, and the ratio of the two is $2/\ln n$ — the same logarithm that appeared in the width. The profile the curves collapse onto is known in closed form: Persi Diaconis, Ron Graham and John Morrison computed it in 1990, and it is the distance between two normal distributions whose means are separated by an amount that decays exponentially along the window.

That profile is what makes “how many steps” a question with a crisp answer. For a small chain the question depends on the threshold chosen; for a large chain with cutoff, every threshold between near-zero and near-one gives the same answer to within the window, and the window is a vanishing fraction of the answer.

A family with no cliff #

Not every family has cutoff, and the control makes the phenomenon visible by its absence.

On a ring of $m$ vertices the walk needs about $m^2$ steps to spread round the ring, which is the diffusive square law: a random walk travels a distance $d$ in about $d^2$ steps. Measured in units of $m^2$, rings of every size trace the same curve, and it is a slope, not a cliff. The fall from $0.9$ to $0.1$ takes about $0.19\,m^2$ steps at every size, a fixed share of the mixing time.

The reason is that the ring’s slowness has only one scale. Its distribution after $t$ steps is a bump of width $\sqrt t$, spreading until it covers the ring; there is no hidden quantity accumulating and then being released. The cube is different in exactly that respect: its walk is spreading in $n$ independent directions at once, and cutoff is what happens when many independent small forgettings all have to be complete before the whole is.

Window against wait #

The definition of cutoff can be read as one ratio: the width of the fall divided by the time to mix. A family has cutoff when that ratio goes to zero.

The table puts the three families side by side. For the riffle shuffle the ratio falls from $0.78$ for thirteen cards to $0.33$ for four hundred and sixteen; for the cube from $1.27$ to $0.72$. For the ring it settles at $1.97$ and stays. Both shrinking rows shrink slowly — like one over the logarithm of the size — and that is why cutoff went unnoticed for so long. It was first named as a phenomenon by David Aldous and Persi Diaconis in 1986, after Diaconis and Mehrdad Shahshahani had found it in 1981 for the shuffle that swaps two random cards, at $\tfrac12 n \ln n$ swaps.

Seeing the cliff from below #

A cliff has two sides, and each is proved by a different argument. The lower side — the chain is still far from random before $t_n$ — needs a question that the chain answers wrongly until then.

For the cube the question is simply how many coordinates are 1. For a uniformly random corner that count is $n/2$, give or take $\sqrt n/2$ — the wobble that does not settle, the standard deviation of a sum of fair coins. For the walk started at the all-zero corner, after $t$ steps the expected count is $\tfrac n2 (1 - (1 - 1/n)^t)$, still short of $n/2$ by about $\tfrac n2 e^{-t/n}$. Measured in standard deviations, that shortfall is $\sqrt n\, e^{-t/n}$, a straight line on a logarithmic axis starting at $\sqrt n$.

It reaches one — where counting the 1s stops being able to tell the walk from random — at $e^{-t/n} = 1/\sqrt n$, that is, at $t = \tfrac12 n \ln n$. The location of the cliff is the time for an exponential decay to beat a square root. The walk’s memory is a quantity of size $n$ decaying by a factor $e^{-1}$ every $n$ steps, and random noise of size $\sqrt n$ hides it once it has shrunk that far. A decay of $n$ to $\sqrt n$ takes $\tfrac12 \ln n$ lifetimes, and that half is the half in $\tfrac12 n \ln n$.

For the riffle shuffle the same role is played by the count of rising sequences: a deck riffled $k$ times has at most $2^k$ of them, a random deck has about $n/2$, and until $2^k$ is comfortably above $n$ the count gives the deck away. That is where the $\log_2 n$ in the shuffle’s cutoff comes from, and the extra factor of $\tfrac32$ comes from the fluctuations, exactly as the square root did for the cube.

Seeing it from above, twice too late #

The upper side — the chain is close to random after $t_n$ — needs a guarantee that holds for every question at once, and the standard tool is a coupling.

The cube’s walk has an especially clean one. Each step picks a coordinate and gives it a fresh random bit; so the moment every coordinate has been picked at least once, the corner is exactly uniform, whatever it started as. The distance from random is therefore at most the chance that some coordinate has not yet been picked — the coupon collector’s question, which has its own sharp threshold at $n \ln n$ picks.

So the bound has a cliff too, but in the wrong place: at $n \ln n$, twice the true $\tfrac12 n \ln n$. The discrepancy is the same square root. At the true cutoff, about $n e^{-t/n} = \sqrt n$ coordinates are still unpicked, all still at zero — and $\sqrt n$ zeros too many is exactly what the binomial’s fluctuation can absorb. Waiting for every last coordinate asks for far more than randomness needs. A coupling that waits for every coordinate proves the right shape and the wrong constant, and closing that factor of two took a separate argument, which is typical: the matching upper bound in a cutoff proof is usually the hard half.

When there is a cliff #

There is a simple necessary condition, noticed by Yuval Peres. A family with cutoff must have its mixing time much longer than its relaxation time, one over the spectral gap. The gap measures how fast the distance falls once it is already falling; the mixing time measures how long until it starts. If the two are comparable, there is no room for a long plateau followed by a short drop.

The three families obey it. The ring’s gap is about $\pi^2/m^2$ and its mixing time about $m^2$, so their product stays bounded — and the ring has no cutoff. The cube’s gap is $1/n$ and its mixing time $\tfrac12 n \ln n$, a product of $\tfrac12 \ln n$ that grows without bound. The riffle shuffle’s gap is one half and its mixing time grows like $\log n$. Both have cutoff.

Peres’s condition is not sufficient in general — Aldous built a family that satisfies it and has no cutoff — but it is sufficient for large classes of chains, including all birth-and-death chains, proved by Jian Ding, Eyal Lubetzky and Peres in 2010. The deepest positive result is Lubetzky and Allan Sly’s of the same year: the walk on a random regular graph has cutoff, at the time a walk on the infinite tree the graph locally resembles needs to get as far from its start as a typical pair of vertices in the graph are from each other. Whether a general criterion exists is still open, and the question of which natural chains have cutoff is one of the most active in the subject.

A cousin in random graphs #

The same shape turns up in a place that looks unrelated. A property of a random graph that switches on as the edge probability rises can do so over a range that is a fixed fraction of the threshold, or over a range that shrinks relative to it — a threshold that is sharp or merely a threshold. A sharp threshold is a cutoff in the edge probability rather than in time, and the reasons coincide: a sharp threshold comes from a property that depends on many independent small events, like the cube’s coordinates, and a coarse one from a property that a single local event can decide, like the ring’s single diffusing bump.

The cube’s walk is also the walk of counting in a code that changes one digit at a time, made random: each step changes one coordinate, and cutoff is the statement that a random such walk goes from knowing its start to knowing nothing in a window of $n$ steps around $\tfrac12 n \ln n$.

What the figures cannot show #

Cutoff is a limit and every figure is finite. The largest cube here has $1{,}024$ dimensions and the largest deck $416$ cards, and on both the fall still takes a sizeable share of the mixing time. The figures show the steepening and the trend in the ratio; they cannot show the limit, and a family could in principle steepen for a while and then stop.

The exact computations depend on symmetry. The deck’s distance is a sum of $n$ terms only because Bayer and Diaconis’s formula depends on the ordering through one statistic, and the cube’s is a chain on $n + 1$ states only because the walk from a corner is symmetric. A chain without such structure, like the walk on a random regular graph, has cutoff that can be proved and not drawn.

And the threshold of a quarter is still a convention. Cutoff is exactly what makes the convention harmless — for a family with a cliff, any threshold gives the same answer to leading order — but the figures report one number per threshold, and the hero’s seven-or-eight is the residue of that choice at a size where the cliff is not yet a step.

Still open: a criterion for the cliff #

With this essay the questions about how a chain approaches its long run are all asked: where it settles, how fast, what bounds the rate, and the shape of the approach across a family. The question that is not answered is the one Peres posed: which families have cutoff. His product condition is necessary and, for chains in general, not sufficient; for which natural classes it suffices — random walks on expanders, on graphs that look the same from every vertex — has been settled for some and is open for others.

What remains beyond that is either about specific chains — cutoff for card shuffles by other rules, for walks on particular groups — or about chains as tools, which a walk that samples a distribution takes up.

What is worth carrying away #

A limit theorem about a single chain describes a slope, and a family of chains can hide a cliff inside it. The cliff sits where an exponentially decaying memory falls below the square-root noise that randomness has anyway, and it is as narrow as the time the memory takes to decay by one factor of $e$.

The habit worth keeping is to ask what a quantity looks like on a rescaled clock. A mixing time reported as one number hides whether the chain approaches randomness gradually or all at once, and the difference is the difference between a threshold that is a matter of taste and one that is a fact about the chain.