Optimal logarithmic mixing of the Thorp shuffle

What OpenAI claims

Proves that the Thorp shuffle randomizes N=2^d labeled cards in Θ(log N) physical shuffles, settling its optimal mixing order for power-of-two deck sizes. Convergence is in total variation from the worst initial ordering and concerns the entire permutation, not just individual card positions. (Lean)

Papers (12)

1. Optimal-order mixing of the Thorp shuffle

   26 September 2026 · Preprint, not peer reviewed · PDF

   We prove that the Thorp shuffle on 2^d cards mixes in Θ(d) complete shuffles. The full permutation law after 1600d shuffles converges to uniform in total variation as d → ∞, uniformly over the initial deck, while a support count gives a lower bound of 2d-O(1).

2. Random coordinate frames and partial permutation laws

   26 September 2026 · Preprint, not peer reviewed · PDF

   For the Thorp shuffle on 2^d cards, we prove that the worst-start total-variation distance after 32800d physical shuffles tends to zero as d → ∞. Combining our fixed-list estimate with the companion Fourier transfer improves this bound to 512d shuffles. These results follow from bounds on partially observed permutation laws in random coordinate frames.

3. From partial permutation information to Fourier bounds

   26 September 2026 · Preprint, not peer reviewed · PDF

   We show how information about partial permutations controls full permutation laws. Let n tend to infinity through multiples of eight. If the images of a uniformly chosen 7n/8 labels approach the uniform injection law in average total variation, and the sign mean tends to zero, then the product of two independent permutations with the given law converges to uniform on Sn.

4. Conditional information under deterministic coordinate sweeps

   26 September 2026 · Preprint, not peer reviewed · PDF

   We bound the information remaining after paths of specified cards in the Thorp shuffle on n=2^d cards have been observed. After a fixed number of deterministic coordinate sweeps, the joint endpoint law of further cards is close to uniform on the available positions, on average over the observed paths, provided a fixed positive fraction of labels lies outside both lists. Combined with a Fourier transfer, these bounds give full-deck mixing after 2048d physical shuffles.

5. Conditional permutations in a revealed switching environment

   26 September 2026 · Preprint, not peer reviewed · PDF

   Fix half the labels in a Thorp shuffle on 2^d positions and reveal their complete trajectories. We prove that, after an explicit absolute number of coordinate sweeps, the conditional permutation of the remaining labels approaches uniform in expected total variation as d → ∞, uniformly in the initial layout. The resulting constructions give full-deck mixing in a constant multiple of d physical shuffles.

6. Routing densities and representation contraction for Thorp sweeps

   26 September 2026 · Preprint, not peer reviewed · PDF

   For N=2^d cards, we prove that an absolute number of coordinate sweeps of the Thorp shuffle brings the full permutation law to total-variation distance tending to zero from uniform. The mixing time therefore has optimal order Θ(log N) in physical shuffles.

7. Row–column symmetry and contraction of coordinate sweeps

   26 September 2026 · Preprint, not peer reviewed · PDF

   We prove that the Thorp shuffle on N=2^d labeled cards has full-permutation total-variation mixing time Θ(log N) in physical shuffles. An absolute number of coordinate sweeps suffices for the upper bound.

8. Random-subspace tests and trace smoothing for coordinate sweeps

   26 September 2026 · Preprint, not peer reviewed · PDF

   We prove that an absolute number of coordinate sweeps of the Thorp shuffle on n=2^d positions brings the full permutation to total-variation distance at most 1/2n^-5 from uniform, uniformly over the initial deck. Thus O(d) physical shuffles suffice, which is optimal in order.

9. Compatibility entropy and the spectrum of a Thorp sweep

   26 September 2026 · Preprint, not peer reviewed · PDF

   We prove that the Thorp shuffle on n=2^d cards mixes in Θ(d) physical shuffles. After a sufficiently large fixed number of coordinate sweeps, the total-variation distance of the full permutation from uniform tends to zero as d → ∞.

10. Signed tensor densities and diagram budgets for the Thorp shuffle

    26 September 2026 · Preprint, not peer reviewed · PDF

    We prove that a fixed number of coordinate sweeps of the Thorp shuffle on 2^d cards makes the squared L2 distance of the full permutation density from uniform tend to zero as d → ∞. In particular, the total-variation mixing time is Θ(d) physical shuffles.

11. Conditional coordinate sweeps and analytic transfer

    26 September 2026 · Preprint, not peer reviewed · PDF

    For coordinate sweeps with near-uniform line laws and line sizes among powers of two in a suitable fixed interval, we prove a Schatten-moment bound after conditioning on any feasible collection of prescribed card trajectories. An analytic transfer to binary sweeps then shows that a fixed number of sweeps mixes the Thorp shuffle on 2^d cards in O(d) physical steps, matching the order of the support lower bound.

12. A strict four-row permanent inequality and permutation moments

    26 September 2026 · Preprint, not peer reviewed · PDF

    We prove a permanent inequality with exponent strictly below two for laws on S4 sufficiently close to uniform and with exactly uniform coordinate marginals. 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=2^d cards to total-variation distance tending to zero from uniform as N → ∞. Thus the mixing time has the optimal order O(log N) in physical shuffles.

Status

Preprint. The papers have not been independently reviewed. Treat the result as OpenAI's claim until other mathematicians have checked it. If a video exists, it illustrates the statement; it is not the proof.