mariuscomper.ukRO

Playing cards, magic and probability

Three shuffles won’t hide a card

Cut a new deck and let the halves fall into each other, three times. Then push one card into the middle. You can find it again, as magicians did more than a hundred years ago. Try it below, then see how many shuffles it really takes to hide one.

Find the card

On this page the deck is shuffled on the table in front of you. Below, the figure shows the same thing on paper: a new deck after three shuffles, with one card moved.

Why the card gives itself away

A shuffle on the table does two things. It cuts the deck into two piles, then lets cards fall from both into one. Neither pile is reordered: cards from the top pile land in the order they had, and so do cards from the bottom pile. A new deck shuffled once is therefore two ordered runs, woven together. Mathematicians call such a run a rising sequence. Here, each one is a thread.

Each shuffle can at most double the number of threads: one, two, four, eight. That is certain, whoever’s hands are doing the shuffling. After three shuffles the deck has at most eight threads, about six and a half cards each on average. Move one card and, usually, it no longer fits on any thread. It sits alone.

10561075A2J6J310J47Q8Q56K9Q 6K77A2A88JQK23104998AK3235494
A new deck after three shuffles in the model, with the top card pushed into the middle. Eight threads; the card alone, circled, is the one that moved: the 6 of hearts.

Magicians found this before mathematicians did. The earliest use Dave Bayer and Persi Diaconis could find is a “card reading” published in 1912 by C. O. Williams, with a prearranged deck shuffled once. The American Charles T. Jordan, whom they describe as an inventor of magic, radio designer, contest winner and chicken farmer, went further. In 1916 he described a feat of “long distance mind reading”: you post someone a deck, they shuffle it, choose a card, shuffle again and send back half the pack, and you write back naming their card.

Jordan’s trick Premo, as Bayer and Diaconis describe it, runs like this. A spectator cuts and shuffles twice and cuts again, takes the top card, looks at it and pushes it into the pack, then cuts and shuffles once more. The magician spreads the cards on the table, stares at them, and names the chosen card.

How long the trick keeps working

Persi Diaconis left home at 14 to tour with the magician Dai Vernon, a master of sleight of hand, and later took a doctorate at Harvard. With Dave Bayer he put Jordan’s trick on a computer: a million deals for each number of shuffles, the card moved after the last one. After three shuffles, a single guess found the card 84% of the time, and two guesses 94%. After four, 29%. “Already at four shuffles,” they wrote, “this trick is terrible magic.”

The version on the table above is simpler: no cuts, and the card moved after the last shuffle. In our simulation, the moved card is the only card without a thread 89% of the time after three shuffles, 23% after four and 1% after five.

How often the moved card is found, by number of shufflesLines: Bayer and Diaconis, one guess and 26 guesses; dotted line: the version on the table above. Below four shuffles one guess nearly always finds it; at four, 29%; after eight, 26 guesses still win 54.8%.0%25%50%75%100%12345678910shuffles26 guesseschance, 26one guesschance, one84%29% · “terrible magic”54.8%dotted: the table above
Solid lines: Bayer and Diaconis’s simulation (1992), with cuts, the card moved after the last shuffle. Dotted line: the version on the table above, without cuts (our simulation). Thin lines show pure chance: 1 in 52 for one guess, 1 in 2 for 26.

But the eye gives up long before the order is gone. Allow yourself 26 guesses, half the deck, and bet even money that the moved card is among them. With a perfectly shuffled deck you win half your bets. After eight shuffles you still win 54.8% of them. The order is still there. You just can’t see it.

Why seven

How do you measure how far a deck is from random order? Bayer and Diaconis used the total variation distance. Think of the best bet anyone could make about the order of the cards. The distance is the difference between the chance that bet wins on the shuffled deck and the chance it wins on a perfectly shuffled one. At 1, the shuffled deck can be told apart every time; at 0, never.

They found an exact formula for the chance of each order after any number of shuffles, and it depends only on the number of threads. From it, the distance for 52 cards can be computed exactly. We redid the calculation and got their table. The distance stays at 1.000 up to four shuffles, falls to 0.924 at five and 0.614 at six, then roughly halves with each shuffle: 0.334, 0.167, 0.085, 0.043. Seven is the first number of shuffles at which it drops below one half. That, L. N. and L. M. Trefethen note, is where the rule comes from.

Total variation distance after m shuffles, 52 cardsIt stays at 1 up to four shuffles, then 0.924, 0.614, 0.334 at seven, the first value below one half, 0.167, 0.085, 0.043.0.00.51.012345.9246.6147.3348.1679.08510.04311.02212.011one halfshuffles
Computed exactly from Bayer and Diaconis’s formula (1992); the values for 1–10 shuffles match their table.

Who says what about “seven”:

  • Aldous and Diaconis, 1986. The analyses “suggest that seven riffle shuffles are needed to get close to random.” It is the earliest printed statement of the rule we found.
  • Bayer and Diaconis, 1992. For large decks, about (3/2)·log2n shuffles for n cards. For 52 cards the formula gives 8.55.
  • Trefethen and Trefethen, 2000. Measure the information left instead of bets, and 3.52% remains after five shuffles, 0.92% after six.
  • Assaf, Diaconis and Soundararajan, 2011. If you only care about some features, such as colours, fewer will do. The bottom card alone is about as well mixed after four shuffles as the whole deck after seven.
  • Diaconis, 2003. “Seven shuffles suffice” is just a rough guide.

Most people, Diaconis told Gina Kolata of The New York Times in 1990, shuffle three or four times.

Neater hands don’t help

The model behind all these numbers was proposed by Edgar Gilbert and Claude Shannon, in a 1955 Bell Laboratories memorandum, and independently by Jim Reeds in 1981. In it, each card drops from one half or the other with a chance in proportion to how many cards each half still holds. Diaconis’s experiments found that it is a good description of how real people shuffle.

Real hands still differ. Professional dealers, Aldous and Diaconis wrote, drop single cards 80% of the time and pairs about 18%; less practised shufflers drop single cards about 60% of the time. Neat is not the same as random. A perfect shuffle, one card from each half in strict turn with the top card staying on top, has nothing random about it: eight of them bring a 52-card deck back to where it started.

The other common way to shuffle, sliding small packets from one hand to the other, is far slower. Robin Pemantle showed in 1989 that a number of shuffles on the order of n²·log n is enough. For 52 cards, Diaconis reckons, that means more than 2,500.

Machines don’t escape either. A manufacturer of casino equipment asked Diaconis, Jason Fulman and Susan Holmes whether one pass through its shuffler, a box with ten shelves, gave a well-shuffled deck. It did not: a player who knew how the machine worked, and was shown each card after guessing, could guess about 9.3 cards of a 52-card deck correctly, against 4.5 for a well-shuffled one. The company’s president replied: “We are not pleased with your conclusions, but we believe them.” The fix was to put the deck through the machine twice.

Unique long before random

A 52-card deck can be put in 52! orders: 80,658,175,170,943,878,571,660,636,856,403,766,975,289,505,440,883,277,824,000,000,000,000, about 8 × 1067. It is often said that a shuffled deck is in an order nobody has ever held. That is true only if the deck is well shuffled, and “well” can be calculated.

From Bayer and Diaconis’s formula we calculated the exact chance that two decks, shuffled the same number of times from new-deck order, end in the same order. Suppose, generously, that 1020 decks have been shuffled that way in all of history: ten billion people, one deck a second, for three centuries.

Decks shuffled m times, all starting from new-deck order
mChance two decks matchMatching pairs expected among 1020 decks
12.2 × 10−16≈ 1.1 × 1024
24.9 × 10−32≈ 247 million
34.7 × 10−47≈ 2.3 × 10−7
42.7 × 10−58≈ 1.4 × 10−18
59.3 × 10−65≈ 4.7 × 10−25
72.5 × 10−68≈ 1.3 × 10−28

After two shuffles, matching pairs would number in the hundreds of millions. After three, the chance of even one falls to about 1 in 4.3 million. After seven, two decks match only about 2 times as often as two perfectly shuffled ones. So, in the model, a deck shuffled three times almost certainly matches no other deck shuffled three times from new-deck order, and yet a magician can still find the card you moved. Unique is not the same as random.

That holds for the model. Real hands are not the model: someone who shuffled with perfect neatness would make the same order every time.

Do it tonight, with a real deck

  1. Put a 52-card deck in an order you know by heart. For instance: spades from ace to king, then hearts, clubs and diamonds.
  2. Hand the deck to someone. Ask them to cut it roughly in half and let the halves fall into each other, three times, with no other cuts in between.
  3. Turn your back. They take the top card, look at it and push it somewhere into the middle of the deck.
  4. Spread the cards face up. Start from the ace of spades and look for the 2, then the 3, always further to the right. When the next card isn’t to the right, start a new thread from the left. The card that fits no thread is theirs.

Three shuffles cannot make more than eight threads, whoever does the shuffling.

And when the cards are for a real game: seven shuffles.

Sources and method

The shuffles on the table follow the Gilbert–Shannon–Reeds model: the cut falls where you tap or, if you press Shuffle, at a binomially distributed point; then each card drops from one half or the other with a chance in proportion to how many cards that half still holds. Threads are Bayer and Diaconis’s rising sequences: the next card in new-deck order continues the thread if it lies further down than the one before.

We computed the total variation distance exactly from Bayer and Diaconis’s formula and Eulerian numbers; it matches their first table to the last decimal. We repeated their simulation of the trick (40,000 deals per number of shuffles, the card moved after the last shuffle): the largest gap from their table is 0.3 percentage points for a single guess and 0.6 for 26 guesses. Figures for the version on this page (no cuts, the lone card) come from 40,000 deals per point. The chance that two decks end in the same order is the sum of the squared probabilities from the same formula; it is exact for the model, not for any particular pair of hands.

Also about chance and order, on this site