# Riffle Shuffle

https://riffle-shuffle.skillsafe.ai/

An interactive page about how many riffle shuffles it takes to randomise a deck
of 52 playing cards. Everything runs in the browser; there is no account, no
server call and no language model behind it.

## What it does

1. **Shuffle** — riffles a real Gilbert-Shannon-Reeds deck (cut binomially, drop
   from each packet with probability proportional to its remaining size) and
   colours the *rising sequences*: the runs of cards whose original order
   survived. One riffle can leave at most two, m riffles at most 2^m, and that
   ceiling is the whole reason a lightly shuffled deck is guessable.
2. **Guess** — the card-guessing game of Bayer & Diaconis section 5.1. You guess
   the top card, it is revealed and discarded, and you guess again. A uniformly
   random deck gives the best possible guesser 4.538 cards out of 52. After one
   riffle the published average is 31.17.
3. **The cutoff** — the exact total variation distance against shuffle count,
   computed from Theorem 1's closed form with exact integer arithmetic, drawn
   beside the values printed in Table 3 of the 1992 paper. All 70 cells match.
4. **How many?** — the same deck scored against twelve different definitions of
   "randomised", and a control shuffle that needs twenty times as many steps.

## The headline

"A few good shuffles randomises a deck" has no single number behind it. For a
52-card deck the answers run from **4 to 13**, and which one you get depends on
the question:

| question | shuffles |
| --- | --- |
| where one named card ended up, to within 1/2 in total variation | 4 |
| where one named card ended up, to within 1/4 | 5 |
| a card counter's edge below one extra card in 52 | 6 |
| under 1% of the deck's original 225.58 bits of information left | 6 |
| total variation under 1/2 — **the famous seven** | 7 |
| under one bit of information left | 7 |
| a card counter's edge below half a card | 7 |
| total variation under 1/4 — the usual textbook mixing time | 8 |
| where one named card ended up, to within 1% | 10 |
| separation distance under 1/2 (no arrangement twice short-changed) | 11 |
| total variation under 1% | 13 |
| separation distance under 1/4 | 13 |

The famous seven is the first shuffle count at which total variation drops below
one half. Trefethen & Trefethen say so in as many words: that threshold is the
origin of the quotation. The textbook convention for a mixing time uses 1/4
instead and gives 8. The asymptotic theorem, (3/2)log2 n, gives 8.55 for 52 cards
— the exact finite-deck answer is smaller than the formula, and the same is true
of the control shuffle.

## The control

Top-to-random — lift the top card, push it back in at a random place — mixes far
more slowly. From the same code, the same metric and the same brute-force
enumeration check, it needs **151** repetitions to bring total variation below
one half, and 179 to bring it below a quarter. Aldous and Diaconis proved the
mixing time grows like n log n, which for 52 cards is 205.5.

## Sources

* Bayer & Diaconis, "Trailing the Dovetail Shuffle to its Lair", Ann. Appl.
  Probab. 2(2), 1992, 294-313.
* Trefethen & Trefethen, "How many shuffles to randomize a deck of cards?",
  Proc. R. Soc. A 456(2002), 2000, 2561-2568.
* Gilbert, "Theory of shuffling", Bell Labs technical memorandum, 1955; Reeds,
  unpublished, 1981.
* Aldous & Diaconis, "Shuffling cards and stopping times", Amer. Math. Monthly
  93(5), 1986, 333-348.

Independent reimplementation. Full credits in /CREDITS.txt.