Shuffling shenanigans

When Persi Diaconis was a kid, his favorite hangout was the magic store. He and his friends goofed around, practiced their tricks and longed for the books and tools.

Then one day, in walked the world’s greatest living magician.

Diaconis, a thirteen-year-old whippersnapper, decided to show off his card tricks. The great magician, Dai Vernon, was so impressed that he decided to teach the teenager a few new things. Each time the pair met in the shop, Vernon taught Diaconis a bit more. And within a year, Vernon offered to take Diaconis on the road with him.

Diaconis didn’t think twice. He packed his bag, met Vernon on the corner and became a professional magician at age 14.

As Diaconis learned the card tricks, he found himself asking questions. How many different ways can you arrange the cards in a deck? What if you ignore the number and suit and only consider card color – then how many different ways can you arrange the deck? Vernon taught Diaconis a sneaky trick to deal the cards out to four players while making sure that all the aces would end up in his own hand. Then Diaconis wondered how he could do the trick with five players.

To answer questions like those, Diaconis eventually realized, he needed mathematics. So he went back to school.

Now he’s a mathematician at Stanford University and one of the world’s greatest experts in probability, the study of chance. But he hasn’t left his magic days behind. Even today, he says, much of his research is motivated by questions about shuffling cards. “Sometimes it’s a little embarrassing,” he says.

A trick explained

In 1992, Diaconis and his friend Dave Bayer of Columbia University finally answered a question that had bugged Diaconis since he was a kid: How many times do you need to shuffle the cards in a deck to make sure they’re all mixed up?

It all got started when Bayer saw Diaconis perform a magic trick. Diaconis started with a deck of cards with each suit in perfect order, ace through king. He handed the deck to someone in the audience. Cut and shuffle the deck three times, he said, and then look at the top card without showing anyone.

“I’m sure you’ll agree that no living human could know the value of that card,” Diaconis declared grandly.

Then Diaconis asked the audience member to insert that card anywhere in the deck and cut and shuffle it a final time.

Finally, he spread the cards face up in a wide arc on the table, stared for several long moments, and plucked out the right card.

“How did you do it?” Bayer asked in amazement.

Diaconis winked at Bayer and, since he was a friend, explained how it worked – once the two were alone. Diaconis put the deck in order again and cut the deck and shuffled the cards once. Then he spread the cards out on the table, face up.

“Look at just the hearts,” he said. Because the cards were in order to begin with, Bayer could clearly see rising sequences of hearts, such as 3, 4, 5, 6, with cards from other suits mixed between the sequences. And if he looked at just the clubs, the diamonds or the spades, ignoring the other suits, he could see the same thing.

Diaconis swept the cards up again, leaving the order the same. Then he cut, shuffled and spread them out again. And again, Bayer saw rising sequences of cards – the sequences were just shorter this time.

“The same thing is true after the third shuffle,” Diaconis said. “But the moved card is usually all by itself, not part of a rising sequence. Once you know the pattern, the moved card usually stands out.”

Bayer admired the trick for a moment and then he had a realization. He could use the card trick to figure out the answer to Diaconis’ old question: How many times should you shuffle a deck?

Counting shuffles

If the cards in a deck are perfectly mixed, their order is random: There are no patterns anyone could use to guess what the next card will be. Diaconis’ trick relied on detecting a pattern in the cards that the moved card didn’t fit into. So in a perfectly mixed deck, Diaconis’ trick wouldn’t work at all.

What Bayer figured out is that if he knew just how often this trick worked, he’d have a way of figuring out how well mixed the deck was.

To calculate that precisely, though, Bayer would have to make Diaconis perform his trick thousands and thousands of times. That seemed kind of mean. So, instead, Bayer decided to teach the trick to someone a lot more patient: a computer.

The computer shuffled the deck some number of times, remembered what the top card was, put that card somewhere else and shuffled again. Then the computer used Diaconis’ method to try to pick out the card that had been moved and then check to see if it got the right answer. It repeated the trick over and over and over, with different numbers of shuffles.

After the first few shuffles, the computer almost always picked the right card since the deck wasn’t very random. And no matter how many times the cards were shuffled, the computer always managed to pick the right card at least a little more often than 1 in 52 times — the probability expected for a perfectly random deck. So the deck never got absolutely, perfectly mixed.

After seven shuffles, though, the deck suddenly became pretty well mixed. The computer picked the right card only about 1.5 times in 52.

“Shuffling cards is like mixing marble pound cake,” Bayer says. “For a long time, there are clear streaks of black and white. Then, all of a sudden, it turns brown.”

The computer program wasn’t enough to prove that seven shuffles was the right number, though. To do that, it would have had to find out how well the trick works for every possible arrangement of cards.

But there’s a problem with that. “There are more ways to arrange 52 cards than the number of particles in the universe,” Diaconis says. “So even if all the atoms in the world were little computers, computing for a long time, they’d never run through all the arrangements.”

The only way to know for sure that seven shuffles got it sufficiently mixed was to use mathematics, because with math, you can reason about all the arrangements at once.

With a lot of hard work, Diaconis and Bayer worked out a formula that told them how random a deck was after any number of shuffles. Just as the computer had hinted, the formula showed that after seven shuffles, the deck was pretty well mixed, ready for a game of cards.

This result shocked casinos and bridge players because they’d mostly been shuffling many fewer times. Even drug manufacturers were interested. Mixing two drugs together into a single pill, it turns out, is a bit like shuffling cards.

Making Old Maid fit

Diaconis couldn’t stop thinking about one card game, though: Old Maid. Old Maid is special, he realized, because the suit doesn’t matter. Each time you get two cards whose numbers or face values match, you take the pair out of your hand, regardless of what suits they are. Before the game begins, one of the queens is removed from the pack. So you hope you don’t get stuck with the queen that doesn’t have a pair!

Because the suits don’t matter, the deck doesn’t have to be quite as random. Suppose, say, that a deck had all the numbers mixed up, but every fourth card was always a heart. That deck wouldn’t really be random, but it would still be good enough for Old Maid.

So Diaconis wondered, how many times do you have to shuffle for card games like that?

Diaconis mentioned the question over lunch one day to a new friend of his, Sami Assaf of the Massachusetts Institute of Technology. She was intrigued. “Most of the math I work on is really hard and abstract, so it was fun to think about a problem I could explain to my friends,” she says.

This time, the researchers didn’t use computers at all. “That might have been smarter,” Assaf says, “but neither of us knew how to do it.” Bayer had done all the computer work in the previous project.

Instead, she made up a smaller deck (with only four cards, say), and shuffled and dealt and shuffled and dealt. With fewer cards, the mathematics was simpler. She and Diaconis used her understanding of these simpler cases to develop a formula that predicted how random the deck would be, ignoring suits.

This time, it turned out that just four shuffles were enough.

So the next time you play Old Maid, be sure to shuffle at least four times. But if you’re playing Crazy Eights, where suits do matter, don’t stop until you get to seven.

Diaconis says there are still lots and lots of questions about shuffling that no one in the world can answer. Perhaps learning some magic tricks will inspire you to answer one!

---

Going Deeper:

Additional Information

Question Sheet: Shuffling Shenanigans

SCIENCE

Before reading:

1. How do you shuffle cards, and what is your particular precise (or imprecise) procedure?
2. How many times do you think you need to shuffle a deck of cards before they’re totally mixed up?
3. Why does it matter?

During reading:

1. What made Persi Diaconis become a mathematician?
2. What does “probability” mean when playing card games?
3. What does it mean for cards to be perfectly random?
4. What is the likelihood that you can pick a desired card, without seeing its face value, from a randomly shuffled deck of regular playing cards (or example: one in X number of tries)?
5. How many times did the Diaconis and Bayer computer program indicate that cards must be shuffled to be completely (or almost completely) random?
6. When you don’t worry about shuffling four suits but only the equivalent of two suits (as in Old Maid), how many shuffles are necessary to get a fairly random ordering of the cards?

After Reading

1. What did Diaconis’ experiments in shuffling have to do with magic? In other words, how does insufficient shuffling aid magicians?
2. What difference does it make whether people know how to shuffle cards into random order? (Hint: What’s at “stake”?)

SOCIAL STUDIES

1. People collectively spend many millions of dollars each year to play games of chance, from cards to roulette. From what you learned in this story, do you think people understand the risks and stakes of their games? And in many instances, games of chance are used to raise money for public goods — such as state education budgets. Explain why you think that is — or is not — a fair use of taxpayer money.
2. What insights did this story give you into the world of magic? Think about the issue of illusion. What was an illusion in the card shuffling and how might it affect an individual’s willingness to spend money on a game of “chance?”