Search

Optimal logarithmic mixing of the Thorp shuffle

Claims the Thorp shuffle on 2^d cards randomizes the whole deck in order d shuffles, the best possible order.

12 papers September 26, 2026 Explained by AI

The Thorp shuffle cuts a deck in half and interleaves the two halves, with a coin flip deciding the order of each matched pair. With 2^d cards, each single card is spread out after d shuffles. The papers claim the whole deck is close to random after 1600d shuffles, and at least about 2d are needed. So the right number is a constant times d. Lean proofs check the main mixing theorem and many supporting estimates.

First step
2008
Ben Morris, the first bound polynomial in d via evolving sets
Significance
Solid
It settles the order of the mixing time for a well-studied shuffle with uses in cryptography.
Trust
Formal proof listed
Field
Probability and statistical mechanics
12 papers

The explanation

Take 8 cards, so d = 3. Cut the deck into two halves of 4. Pair the first card of each half, then the second cards, and so on. For each pair, flip a fair coin to decide which card goes first. Then lay the pairs down in order. That is one Thorp shuffle. Each shuffle uses 4 coin flips, so 3 shuffles give at most 2¹² = 4,096 different orders. But there are 8! = 40,320 orders of 8 cards. So after 3 shuffles, the deck is still far from random, even though each single card is now equally likely to be anywhere. An exact computer count gives a distance from uniform of about 0.898 after 3 shuffles. It falls to about 0.20 after 5 shuffles and 0.026 after 8.

That distance is total variation. It is half the summed gap between the shuffled deck's probabilities and the perfectly random ones. The general lower bound is 1 − 2^(tn/2)/n! after t shuffles of n cards. For n = 8 and t = 3 it gives 1 − 4,096/40,320, about 0.898, matching the exact count. The mixing time is the first t where the distance is at most 1/4. The bound says this takes about 2d − O(1) shuffles at least.

Thorp introduced the shuffle in 1973. For 2^d cards, Morris got the first bound polynomial in d, of order d⁴⁴. Montenegro and Tetali improved it to d²⁹, and Morris later to d³. The obstacle is that single cards mix fast, but the joint order of all n cards holds far more information.

The main paper claims 1600d shuffles bring the whole deck close to random as d grows, from any starting deck. With the lower bound, the mixing time is a constant times d. The constant 1600 is a convenient choice, not a sharp one. The proof labels positions by binary strings, the corners of a cube. It tracks most cards one at a time, then recovers the rest with Fourier analysis on the group of all orders. Companion papers claim other routes to the same order. One gives 512d shuffles. Another reaches distance ½n⁻⁵ after a fixed number of full sweeps. A third uses a new inequality for 4-by-4 permanents.

How sure is this? A computer proof checker called Lean has a formal proof of the main theorem. After 1600d shuffles the distance tends to zero, from every starting deck. Lean also covers the trace-smoothing bound and many supporting estimates, including the four-row permanent inequality. Several papers' full conclusions sit outside their selected Lean statements. No specialist review of these papers has been published.

What it doesn't show. This does not find the exact leading constant or a sharp cutoff. It does not cover decks whose size is not a power of two.

Where it came from

This result comes from an unreleased OpenAI model, published in the openai/math release on 6 October 2026.

Hype check

The headline mixing theorem has a Lean proof. It settles the order, not the exact constant. No specialist review is published.

Words used

Thorp shuffle
Cut the deck in half, pair matching positions, flip a coin for each pair's order, and interleave.
Total variation distance
Half the sum, over all orders of the deck, of the gap between their actual and perfectly random probabilities.
Mixing time
The number of shuffles needed before the deck is within distance 1/4 of uniformly random.
Uniform
Every order of the deck is equally likely.
Fourier analysis on a group
Breaking a probability law on permutations into pieces, one for each basic symmetry pattern, and bounding each piece.
Permanent
Like a determinant of a square matrix, but every term is added with a plus sign.

The original papers (12)

Lean notes

All quoted lines (11)
  1. For every integer t≥0t\ge0, ∥qd∗t−Un∥TV≥1−2tn/2n!.\|q_d^{*t}-U_n\|_{\mathrm{TV}} \ge 1-\frac{2^{tn/2}}{n!}.
    Optimal-order mixing of the Thorp shuffle Back to text
  2. Thorp introduced the model in his 1973 study of the effects of nonrandom shuffling on Faro.
    Optimal-order mixing of the Thorp shuffle Back to text
  3. For dyadic decks, Morris obtained the first bound polynomial in dd, namely O(d44)O(d^{44}), using evolving sets and a chameleon process that tracks conditional card probabilities.
    Optimal-order mixing of the Thorp shuffle Back to text
  4. Montenegro and Tetali sharpened this analysis to O(d29)O(d^{29}) by spectral-profile and evolving-set methods.
    Optimal-order mixing of the Thorp shuffle Back to text
  5. He then proved O(d3)O(d^3) for n=2dn=2^d by a stronger contraction over a block of dd shuffles.
    Optimal-order mixing of the Thorp shuffle Back to text
  6. The full permutation law after 1600d1600d shuffles converges to uniform in total variation as d→∞d\to\infty, uniformly over the initial deck, while a support count gives a lower bound of 2d−O(1)2d-O(1).
    Optimal-order mixing of the Thorp shuffle Back to text
  7. The upper bound is asymptotic in dd; the constant 16001600 is an explicit choice in the proof, not a proposed sharp constant.
    Optimal-order mixing of the Thorp shuffle Back to text
  8. Label positions by binary strings of length dd, the vertices of a cube.
    Optimal-order mixing of the Thorp shuffle Back to text
  9. Combining our fixed-list estimate with the companion Fourier transfer improves this bound to 512d512d shuffles.
    Random coordinate frames and partial permutation laws Back to text
  10. We prove that an absolute number of coordinate sweeps of the Thorp shuffle on n=2dn=2^d positions brings the full permutation to total-variation distance at most 12n−5\frac12n^{-5} from uniform, uniformly over the initial deck.
    Random-subspace tests and trace smoothing for coordinate sweeps Back to text
  11. Applied to a four-row recursion, it shows that an absolute number of coordinate sweeps brings the full permutation of the Thorp shuffle on N=2dN=2^d cards to total-variation distance tending to zero from uniform as N→∞N\to\infty.
    A strict four-row permanent inequality and permutation moments Back to text

Other sources

  1. openai/math, Lean scope note for family 238 The formalization proves optimal-order mixing of the Thorp shuffle on 2d2^d cards.
  2. openai/math release notes (2026): model provenance and review status manuscripts and supporting proof artifacts produced by an internal OpenAI model

Browse Probability and statistical mechanics Open since the 2000sLean-checked resultsSolid results