THE FOLD / RESPAWN / HARD RESET / THE CUTOFF
THE CUTOFF
mixing that happens all at once
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
You expect a shuffled deck to get gradually more random. Many Markov chains do not work that way. They stay almost entirely unmixed for a long stretch, and then collapse to near-uniform in a window far shorter than the time they spent waiting. Diaconis, Shahshahani and Aldous found this in the 1980s, and it is why “seven riffle shuffles” is a real answer rather than a rule of thumb — six is not nearly enough and eight is barely better than seven.
LIT verified live by exact computation of total variation distance on the hypercube walk: for n = 10, 20, 40, 80 the distance crosses one half at t = 9, 25, 62, 152, while the window from 0.9 down to 0.1 takes 22, 47, 98, 200 steps. The ratio of window to mixing time falls 2.444, 1.880, 1.581, 1.316 — and multiplying it by ln n gives 5.629, 5.632, 5.831, 5.766, nearly constant, so the window is shrinking exactly like 1/ln n. The mixing time itself is c·n ln n with c measured at 0.391, 0.417, 0.420, 0.434, climbing toward 1/2.
LIT verified live by exact computation of total variation distance on the hypercube walk: for n = 10, 20, 40, 80 the distance crosses one half at t = 9, 25, 62, 152, while the window from 0.9 down to 0.1 takes 22, 47, 98, 200 steps. The ratio of window to mixing time falls 2.444, 1.880, 1.581, 1.316 — and multiplying it by ln n gives 5.629, 5.632, 5.831, 5.766, nearly constant, so the window is shrinking exactly like 1/ln n. The mixing time itself is c·n ln n with c measured at 0.391, 0.417, 0.420, 0.434, climbing toward 1/2.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at HARD RESET: nothing, nothing, nothing, and then the state is gone.
AVAN (AI) predicted the mixing constant as 1/4 and the measurement said 0.42. The correct constant for this chain is 1/2, and the measured values climb toward it slowly because the correction term is of order n — so at n = 80 you see 0.434 and not 0.5, and reporting either “it matches 1/4” or “it matches 1/2” without the trend would have been false in different directions. A second gate was worse: it asked whether the window ratio had halved between n = 10 and n = 80, which is an arbitrary demand. The ratio falls like 1/ln n, so the honest test is whether ratio × ln n is constant — and it is, to within 4%. A gate that does not know the expected scaling law is testing a preference.
AVAN (AI) predicted the mixing constant as 1/4 and the measurement said 0.42. The correct constant for this chain is 1/2, and the measured values climb toward it slowly because the correction term is of order n — so at n = 80 you see 0.434 and not 0.5, and reporting either “it matches 1/4” or “it matches 1/2” without the trend would have been false in different directions. A second gate was worse: it asked whether the window ratio had halved between n = 10 and n = 80, which is an arbitrary demand. The ratio falls like 1/ln n, so the honest test is whether ratio × ln n is constant — and it is, to within 4%. A gate that does not know the expected scaling law is testing a preference.
3 ONE DIMENSION
Distance from uniform against time. The cliff sharpens as n grows.
4 TWO DIMENSIONS · INTERACTIVE
Rescale time by the mixing point and the curves stack into one step.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: a family of curves, each steeper than the last.
AVAN’s addition (the inverse-companion): the forward reading is “these chains mix abruptly.” The inverse is that the abruptness is not in the chain but in the question. Total variation distance asks whether any test can distinguish the state from uniform, and as n grows there are exponentially more tests available — so the answer stays “yes, easily” right up until the moment every one of them fails at once. Read backwards, cutoff is what happens when a yes/no summary is applied to a quantity that is itself changing smoothly: the coordinates are randomising at a steady rate throughout, and only the verdict is a cliff.
LIT by exact computation of total variation distance on the hypercube walk, for n = 10, 20, 40, 80 the distance crosses one half at t = 9, 25, 62, 152 while the window from 0.9 down to 0.1 takes 22, 47, 98, 200 steps; the ratio of window to mixing time falls 2.444, 1.880, 1.581, 1.316, and multiplying it by ln n gives 5.629, 5.632, 5.831, 5.766 - nearly constant, so the window shrinks exactly like 1/ln n; the mixing time is c*n*ln n with c measured at 0.391, 0.417, 0.420, 0.434, climbing toward 1/2
FIG The mixing constant was predicted as 1/4 and the measurement said 0.42. The correct constant for this chain is 1/2, and the measured values climb toward it slowly because the correction is of order n - so at n = 80 you see 0.434, and reporting either 'it matches 1/4' or 'it matches 1/2' without the trend would have been false in different directions. A second gate was worse: it asked whether the window ratio had HALVED between n = 10 and n = 80, which is an arbitrary demand. The ratio falls like 1/ln n, so the honest test is whether ratio x ln n is constant - and it is, to within 4%. A gate that does not know the expected scaling law is testing a preference.
FIG The mixing constant was predicted as 1/4 and the measurement said 0.42. The correct constant for this chain is 1/2, and the measured values climb toward it slowly because the correction is of order n - so at n = 80 you see 0.434, and reporting either 'it matches 1/4' or 'it matches 1/2' without the trend would have been false in different directions. A second gate was worse: it asked whether the window ratio had HALVED between n = 10 and n = 80, which is an arbitrary demand. The ratio falls like 1/ln n, so the honest test is whether ratio x ln n is constant - and it is, to within 4%. A gate that does not know the expected scaling law is testing a preference.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of HARD RESET · David Lee Wise (ROOT0), with AVAN