Episode 238, October 2026

How many shuffles randomize a deck?

Twelve preprints claim the Thorp shuffle mixes a deck of 2^d cards in order log N shuffles

Covers result 238 in OpenAI’s catalog: all 12 papers. See its connections to other results and the work it cites.

Play Episode 238: How many shuffles randomize a deck? Eight cards, A to H, split into two halves and interleaved.

4:33. English captions available. The video loads from YouTube when you press play.

Chapters

The claim, in plain words

Cut a deck into two halves and pair the first card of each half, then the second, and so on. For each pair a fair coin decides which card goes first, and the pairs are stacked in order. That is one Thorp shuffle, studied by Edward Thorp in 1973; Morris, Rogaway and Stegers later used it to encrypt credit card numbers. In binary, a shuffle drops the top bit of a card’s address, shifts the rest left and appends that bit, flipped or not by the coin, so after d shuffles of 2^d cards any single card is in a perfectly random position. The whole deck takes longer: d shuffles use only d·2^d−1 coins. Diaconis, as Morris reported, called it the longest-standing open card-shuffling problem. Morris proved (log N)⁴⁴ in 2005; Montenegro and Tetali brought the exponent to 29, and Morris to 4 for every even deck and to 3 for powers of two. Jonasson’s 2009 course notes recorded the expectation that the answer is of order log N.

Result 238 is twelve OpenAI preprints, 683 pages, dated September 26, 2026. The main paper claims that for decks of 2^d cards, after 1600d shuffles the full permutation is close to uniform in total variation, from any starting order, as d grows. With the coin-counting lower bound, about 2d shuffles, the mixing time is of order log N, the optimal order.

What it doesn’t claim

The right constant (somewhere between 2 and 1600, or 512 by combining two companion papers), a cutoff (whether the deck randomizes suddenly), or decks whose size is not a power of two, where (log N)⁴ remains the best bound.

Where it stands

Posted as preprints: OpenAI, 12 papers, 683 pages, dated September 26, 2026
Peer reviewed: Not yet
Checked in Lean: Yes, the headline and selected companion statements (docs)

Last checked October 19, 2026. The preprints have not been revised since release. In Lean, thirteen comparators cover statements from across the papers, about 270,000 lines with no unproved steps; one states the headline, mixing time of order log N, from first principles (we did not build it). OSVerify has not reviewed the item. We found no expert reaction; one public project treats the bounds as starting points while it chases the cutoff.

How the proof goes

Sweeps. Undo the rotation of the bits: every d shuffles become one sweep of fair switches across each of the d binary directions.
One card at a time. Follow cards one at a time, given the paths of the cards already placed. A switch with both slots free averages the card’s chances, so the process has a memory of only one sweep. After 200 sweeps a random 7/8 of the deck lands almost uniformly.
Fourier. A law that is nearly uniform on eight suitable large sets of cards, each 7/8 of the deck, has small Fourier coefficients in every high-dimensional representation of the permutation group; the sign is handled by the last coin. Eight blocks of 200 sweeps give 1600.
Other routes. The other eleven papers give several more proofs, most of them self-contained, with headline constants from 512 to 16 million sweeps, side routes as large as about 172 billion, and some with no explicit constant.

The numbers in the video

Ours, exact: after 3 shuffles of 8 cards the whole deck is at distance 0.898 from random, since 12 coins give only 4,096 outcomes against 40,320 orderings; below 1/4 after 5 shuffles (4 cards: 3). Every ordering first becomes possible after at least 2d − 2 shuffles, for every deck from 8 cards to 2⁴⁰.
Ours, exact: for 8 cards, one sweep wipes out 15 of the 21 nontrivial representations of the permutation group; the largest survivor is shrunk to at most 0.354.

Read the source

Optimal-order mixing of the Thorp shuffle (PDF), 14 pages.
Random coordinate frames and partial permutation laws (PDF), 72 pages.
From partial permutation information to Fourier bounds (PDF), 66 pages.
Conditional information under deterministic coordinate sweeps (PDF), 81 pages.
Conditional permutations in a revealed switching environment (PDF), 32 pages.
Routing densities and representation contraction for Thorp sweeps (PDF), 86 pages.
Row–column symmetry and contraction of coordinate sweeps (PDF), 38 pages.
Random-subspace tests and trace smoothing for coordinate sweeps (PDF), 15 pages.
Compatibility entropy and the spectrum of a Thorp sweep (PDF), 128 pages.
Signed tensor densities and diagram budgets for the Thorp shuffle (PDF), 109 pages.
Conditional coordinate sweeps and analytic transfer (PDF), 23 pages.
A strict four-row permanent inequality and permutation moments (PDF), 19 pages.
The Lean formalization notes.
The collection’s catalog, where this is result 238.

The 12 papers in this result

OpenAI groups related papers, such as alternative proofs, supporting results and consequences, into one result; we label the first paper it lists the main paper and the others companions.

Optimal-order mixing of the Thorp shuffle main paper
Random coordinate frames and partial permutation laws companion
From partial permutation information to Fourier bounds companion
Conditional information under deterministic coordinate sweeps companion
Conditional permutations in a revealed switching environment companion
Routing densities and representation contraction for Thorp sweeps companion
Row–column symmetry and contraction of coordinate sweeps companion
Random-subspace tests and trace smoothing for coordinate sweeps companion
Compatibility entropy and the spectrum of a Thorp sweep companion
Signed tensor densities and diagram budgets for the Thorp shuffle companion
Conditional coordinate sweeps and analytic transfer companion
A strict four-row permanent inequality and permutation moments companion

Transcript

Read the full script

0:00The question

Take a deck of eight cards, A to H. Cut it into two halves, and pair the first card of each half, then the second, and so on. For each pair, flip a fair coin to decide which card goes first, and stack the pairs in order. That is one Thorp shuffle, studied by Edward Thorp, of blackjack fame, in 1973. Cryptographers later used it to encrypt short messages like credit card numbers. Write each position in binary. One shuffle drops the top bit of a card’s address, shifts the rest left, and appends that old bit, flipped or not by the pair’s coin. So after three shuffles of eight cards, each card’s address is three fresh coin flips: any single card is in a perfectly random position. How many shuffles until the whole deck, every ordering, is close to random? Not three. Our exact computation for eight cards: after three shuffles the deck is still at distance 0.9 from random, because 12 coin flips give only 4,096 orderings out of 40,320. Counting coins this way, a deck of 2^d cards needs at least about 2d shuffles before every ordering is even possible: at least 2d − 2, for every deck from eight cards up to 2^40. With eight cards, five shuffles bring the distance below one quarter.

1:20The claim

Diaconis, as Morris reported in 2005, called it the longest-standing open card-shuffling problem. That year Morris proved the first polylogarithmic bound, (log N)^44. Montenegro and Tetali brought it to the 29th power, Morris to the fourth for every even deck, and then, for powers of two, to log cubed. Jonasson’s 2009 course notes recorded the expectation that the true answer is of order log N. Result 238 is 12 OpenAI preprints, dated September 26, 2026. The main paper claims that for decks of 2^d cards, after 1600d shuffles the full permutation is close to uniform in total variation, from any starting order, as d grows. With the coin-counting bound, the mixing time is of order log N, the optimal order. Not claimed: the right constant, which lies somewhere between 2 and 1600, or 512 by combining two companions; whether the deck randomizes suddenly, a cutoff; or decks whose size is not a power of two, where log to the fourth remains the best bound.

2:31How the proof goes

First, undo the rotation of the bits: every d shuffles become one sweep of fair switches across each of the d binary directions. Then follow cards one at a time, given the paths of the cards already placed. When a card meets a switch with both slots free, its chances average; this gives the process a memory of only one sweep. After 200 sweeps, a random 7/8 of the deck lands almost uniformly. Then representation theory takes over. A law that is nearly uniform on the right large sets of cards, eight of them, each 7/8 of the deck, must have small Fourier coefficients in every high-dimensional representation of the permutation group; the sign is handled by the last coin. Eight such blocks of 200 sweeps give 1600. In our eight-card computation, one sweep wipes out 15 of the 21 nontrivial representations exactly; the largest survivor is shrunk to at most 0.35. The other eleven papers give several more proofs by different routes, most of them self-contained, with headline constants from 512 to 16 million sweeps, side routes as large as 170 billion, and some with no explicit constant at all.

3:49Where it stands

The preprints are unrefereed and unchanged since release. In Lean, 13 comparators cover statements from across the papers, about 270,000 lines with no unproved steps; one states the headline, mixing time of order log N, from first principles. We did not build it. OSVerify has not reviewed the item. We found no expert reaction; one public project treats the bounds as starting points while it chases the cutoff. If it holds, the whole deck is random after a constant times log N shuffles, the order Jonasson’s notes recorded as expected, and nothing faster is possible. What that constant really is, nobody yet knows.

Spot a mistake?

This episode simplifies on purpose, but it shouldn’t be wrong. If something is, open an issue on GitHub or leave a comment on YouTube. Corrections are noted here with a date.