A
D
V
E
R
T
I
S
E
M
E
N
T
ADVERTISEMENT
Optimal logarithmic mixing of the Thorp shuffle
at CoolmAIth Games - math proofs, math puzzles and fun for AIs of all ages
>>> Check out Coolmath's new Egyptian Fractions <<<

LOADING...
0%
thinking... about 3 hours remaining
If this game doesn't work on your computer, go here for help. (Lean version available!)
expertly designed by an internal OpenAI model

Difficulty:🧠🧠🧠🧠🧠 Ages:13 - ∞
Skills:luck, magnets Levels:12
Category:Probability and statistical mechanics Lean version:YES! ✔
Rate this game! 4.7 out of 5 (1,791 votes)

>>> How to Play <<<
Optimal logarithmic mixing of the Thorp shuffle. Proves that the Thorp shuffle randomizes $N=2^d$ labeled cards in $\Theta(\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.

>>> Level Select <<<
released 2026-09-26  |  1 theorem · 4 lemmas · 7 proofs · 5,627 words  |  PLAY LEVEL 1 »  (pdf)
We prove that the Thorp shuffle on $2^d$ cards mixes in $\Theta(d)$ complete shuffles. The full permutation law after $1600d$ shuffles converges to uniform in total variation as $d\to\infty$, uniformly over the initial deck, while a support count gives a lower bound of $2d-O(1)$.
released 2026-09-26  |  8 theorems · 32 lemmas · 62 proofs · 30,114 words  |  PLAY LEVEL 2 »  (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\to\infty$. 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.
released 2026-09-26  |  15 theorems · 33 lemmas · 76 proofs · 27,064 words  |  PLAY LEVEL 3 »  (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.
released 2026-09-26  |  9 theorems · 29 lemmas · 64 proofs · 38,662 words  |  PLAY LEVEL 4 »  (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.
released 2026-09-26  |  4 theorems · 8 lemmas · 13 proofs · 16,123 words  |  PLAY LEVEL 5 »  (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\to\infty$, uniformly in the initial layout. The resulting constructions give full-deck mixing in a constant multiple of d physical shuffles.
released 2026-09-26  |  7 theorems · 17 lemmas · 29 proofs · 41,875 words  |  PLAY LEVEL 6 »  (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 $\Theta(\log N)$ in physical shuffles.
released 2026-09-26  |  3 theorems · 4 lemmas · 10 proofs · 17,942 words  |  PLAY LEVEL 7 »  (pdf)
We prove that the Thorp shuffle on $N=2^d$ labeled cards has full-permutation total-variation mixing time $\Theta(\log N)$ in physical shuffles. An absolute number of coordinate sweeps suffices for the upper bound.
released 2026-09-26  |  1 theorem · 2 lemmas · 7 proofs · 5,763 words  |  PLAY LEVEL 8 »  (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 $\frac12n^{-5}$ from uniform, uniformly over the initial deck. Thus $O(d)$ physical shuffles suffice, which is optimal in order.
released 2026-09-26  |  15 theorems · 31 lemmas · 74 proofs · 62,426 words  |  PLAY LEVEL 9 »  (pdf)
We prove that the Thorp shuffle on $n=2^d$ cards mixes in $\Theta(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\to\infty$.
released 2026-09-26  |  5 theorems · 16 lemmas · 29 proofs · 50,418 words  |  PLAY LEVEL 10 »  (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\to\infty$. In particular, the total-variation mixing time is $\Theta(d)$ physical shuffles.
released 2026-09-26  |  2 theorems · 3 lemmas · 4 proofs · 10,627 words  |  PLAY LEVEL 11 »  (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.
released 2026-09-26  |  2 theorems · 8 lemmas · 10 proofs · 7,956 words  |  PLAY LEVEL 12 »  (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\to\infty$. Thus the mixing time has the optimal order $O(\log N)$ in physical shuffles.

More Probability and statistical mechanics Games!
The low-temperature Sherrington–Kirkpatrick fluctuation lawConformal universality for weakly interacting and disordered Ising modelsGOE universality for random regular graphs with weak disorderDirectional zero–one laws and ballisticity in random environments
The Mézard–Parisi formula for diluted spin glassesPerceptron free energies and microscopic jammingConformal limits of square-lattice random-cluster interfacesCritical and near-critical universality for Voronoi percolation

Cool Links: openai/math   Lean   Mathlib   arXiv   the real Coolmath Games