Thorp shuffle: how often until the deck is random?
About this app
Cut the deck, one coin per pair: after log₂ N rounds every single card is uniform, the whole deck far from it. Animated shuffling, exact distance for 8 cards over all 40,320 orders, counting bound, riffle comparison, growth over d. Result from openai/math (family 238, formalised in Lean): Θ(log N) rounds suffice.
What it is about
In the Thorp shuffle (Edward Thorp, 1973) you cut the deck in half; cards at the same position in the two halves form pairs, and a fair coin decides for each pair which card goes first. After d = log₂ N rounds every single card is exactly uniform. But when is the whole order random? The known bounds were powers of d, and O(d) was conjectured. An AI-generated preprint in github.com/openai/math (family 238) claims that for N = 2^d cards Θ(log N) rounds suffice. The catalogue lists the main theorem as formalised in Lean; the preprint is not peer-reviewed. The Thorp shuffle is used as a building block in format-preserving encryption.
What the app shows
A deck is shuffled with animation, round by round; you can follow card 1, and a counter shows how many positions it could occupy after t rounds. The distance panel measures how far the distribution is from uniform: for a single card, for the whole deck exactly with 4 and 8 cards over all 40,320 orders, plus the counting bound and the exact riffle value after Bayer–Diaconis. A growth panel plots the rounds needed against d and lists upper bounds from the literature.
What to look for
Shuffle 8 cards and compare the curves: the single-card curve is already zero at t = d, the whole-deck curve is not. For 16 cards and more nobody knows the exact distance of the deck; only a lower bound is shown. What is proved is that at least 2d − O(1) rounds are needed and at most 1600·d suffice; the 1600 is a constant from the proof, not a measurement. A riffle round uses N random bits, a Thorp round only N/2.
Frequently asked questions
- What is the Thorp shuffle?
- The Thorp shuffle is a card-shuffling method by Edward Thorp (1973): the deck is cut into two equal halves, and for each pair of cards at the same position a coin flip decides which goes first. Each round needs only N/2 random bits. That is why cryptography uses it as a building block for encrypting small domains.
- How many times do you need to shuffle a deck?
- It depends on the shuffle. For the usual riffle shuffle, Bayer and Diaconis showed that about 3/2·log₂ N rounds are needed, roughly seven for 52 cards. For the Thorp shuffle the exact mixing time is harder to pin down; each single card is uniform after log₂ N rounds, the whole deck only later.
- Has the mixing time of the Thorp shuffle been proved?
- It was conjectured that O(log N) rounds suffice; only higher powers of log N had been proved. An AI-generated preprint in the catalogue github.com/openai/math (family 238) claims Θ(log N) rounds for N = 2^d cards. The catalogue lists the main theorem as formalised in Lean; the preprint has not yet been peer-reviewed.
- What can I try out in this app?
- You shuffle a deck with animation, round by round, and follow a card. For 4 and 8 cards you see the exact distance of the whole deck from uniform, and for larger decks a lower bound. A comparison with riffle shuffling and an overview of the bounds put the result in context.
Subject: Open problems, solved by AI
More from Open problems, solved by AI
- Anderson localisation: 2D vs. 3D (3D)
- Barker sequences and circulant Hadamard matrices
- Barnette's conjecture: a round trip over every polyhedron (3D)
- Birkhoff billiards: only the ellipse has no gaps
- Cardy's formula — percolation in a random tiling
- The plane is not five-colourable (Hadwiger–Nelson)
- Double-dimer loops and CLE₄
- Triangular billiards — irrational angles mix (3D)
A VisuApp by heyprof: interactive, free in your browser, no sign-up. What is a VisuApp? · All apps