# The Mathematics of . . . Shuffling

#### A magician turned mathematician saves the casinos' shirts

By Dana Mackenzie|Tuesday, October 01, 2002
RELATED TAGS: MATH

 A seemingly random arrangement of cards in a deck is sometimes nothing but an illusion. Persi Diaconis, a Stanford mathematician and practiced magician, can restore a deck of cards to its original order with a series of perfect shuffles. The sleight of hand: Each time Diaconis cuts the cards, he interleaves exactly one card from the top half of the deck between each pair of cards from the bottom half.Photographs by Sian Kennedy

Persi Diaconis picks up an ordinary deck of cards, fresh from the box, and writes a word in Magic Marker on one side: RANDOM. He shuffles the deck once. The letters have re-formed themselves into six bizarre runes that still look vaguely like the letters R, A, and so on. Diaconis shuffles again, and the markings on the side become undecipherable. After two more shuffles, you can't even tell that there used to be six letters. The side of the pack looks just like the static on a television set. It didn't look random before, but it sure looks random now.

Keep watching. After three more shuffles, the word RANDOM miraculously reappears on the side of the deck—only it is written twice, in letters half the original size. After one more shuffle, the original letters materialize at the original size. Diaconis turns the cards over and spreads them out with a magician's flourish, and there they are in their exact original sequence, from the ace of spades to the king of diamonds.

Diaconis has just performed eight perfect shuffles in a row. There's no hocus-pocus, just skill perfected in his youth: Diaconis ran away from home at 14 to become a magician's assistant and later became a professional magician and blackjack player. Even now, at 57, he is one of a couple of dozen people on the planet who can do eight perfect shuffles in less than a minute.

Diaconis's work these days involves much more than nimbleness of hand. He is a professor of mathematics and statistics at Stanford University. But he is also the world's leading expert on shuffling. He knows that what seems to be random often isn't, and he has devoted much of his career to exploring the difference. His work has applications to filing systems for computers and the reshuffling of the genome during evolution. And it has led him back to Las Vegas, where, instead of trying to beat the casinos, he now works for them.

A card counter in blackjack memorizes the cards that have already been played to get better odds by making bets based on his knowledge of what has yet to turn up. If the deck has a lot of face cards and 10s left in it, for instance, and he needs a 10 for a good hand, he will bet more because he's more likely to get it. A good card counter, Diaconis estimates, has a 1 to 2 percent advantage over the casino. On a bad day, a good card counter can still lose \$10,000 in a hurry. And on a good day, he may get a tap on the shoulder by a large person who will say, "You can call it a day now." By his mid-twenties, Diaconis had figured out that doing mathematics was an easier way to make a living.

Two years ago, Diaconis himself got a tap on the shoulder. A letter arrived from a manufacturer of casino equipment, asking him to figure out whether its card-shuffling machines produced random shuffles. To Diaconis's surprise, the company gave him and his Stanford colleague, Susan Holmes, carte blanche to study the inner workings of the machine. It was like taking a Russian spy on a tour of the CIA and asking him to find the leaks.

When shuffling machines first came out, Diaconis says, they were transparent, so gamblers could actually see the cutting and riffling inside. But gamblers stopped caring after a while, and the shuffling machines turned into closed boxes. They also stopped shuffling cards the way humans do. In the machine that Diaconis and Holmes looked at, each card gets randomly directed, one at a time, to one of 10 shelves. The shuffling machine can put each new card either on the top of the cards already on that shelf or on the bottom, but not between them.

"Already I could see there was something wrong," says Holmes. If you start out with all the red cards at the top of the deck and all the black cards at the bottom, after one pass through the shuffling machine you will find that each shelf contains a red-black sandwich. The red cards, which got placed on the shelves first, form the middle of each sandwich. The black cards, which came later, form the outside. Since there are only 10 shelves, there are at most 20 places where a red card is followed by a black one or vice versa—fewer than the average number of color changes (26) that one would expect from a random shuffle.

The nonrandomness can be seen more vividly if the cards are numbered from 1 to 52. After they have passed through the shuffling machine, the numbers on the cards form a zigzag pattern. The top card on the top shelf is usually a high number. Then the numbers decrease until they hit the middle of the first red-black sandwich; then they increase and decrease again, and so on, at most 10 times.

Diaconis and Holmes figured out the exact probability that any given card would end up in any given location after one pass through the machine. But that didn't indicate whether a gambler could use this information to beat the house.

So Holmes worked out a demonstration. It was based on a simple game: You take cards from a deck one by one and each time try to predict what you've selected before you look at it. If you keep track of all the cards, you'll always get the last one right. You'll guess the second-to-last card right half the time, the third-to-last card a third of the time, and so on. On average, you will guess about 4.5 cards correctly out of 52.

By exploiting the zigzag pattern in the cards that pass through the shuffling machine, Holmes found a way to double the success rate. She started by predicting that the highest possible card (52) would be on top. If it turned out to be 49, then she predicted 48—the next highest number—for the second card. She kept going this way until her prediction was too low—predicting, say, 15 when the card was actually 18. That meant the shuffling machine had reached the bottom of a zigzag and the numbers would start climbing again. So she would predict 19 for the next card. Over the long run, Holmes (or, more precisely, her computer) could guess nine out of every 52 cards correctly.

To a gambler, the implications are staggering. Imagine playing blackjack and knowing one-sixth of the cards before they are turned over! In reality, a blackjack player would not have such a big advantage, because some cards are hidden and six full decks are used. Still, Diaconis says, "I'm sure it would double or triple the advantage of the ordinary card counter."

Diaconis and Holmes offered the equipment manufacturer some advice: Feed the cards through the machine twice. The alternative would be more expensive: Build a 52-shelf machine.

A small victory for shuffling theory, one might say. But randomization applies to more than just cards. Evolution randomizes the order of genes on a chromosome in several ways. One of the most common mutations is called a "chromosome inversion," in which the arm of a chromosome gets cut in two random places, flipped over end-to-end, and reattached, with the genes in reverse order. In fruit flies, inversions happen at a rate of roughly one per every million years. This is very similar to a shuffling method called transposition that Diaconis studied 20 years ago. Using his methods, mathematical biologists have estimated how many inversions it takes to get from one species of fruit fly to another, or to a completely random genome. That, Diaconis suggests, is the real magic he ran away from home to find. "I find it amazing," he says, "that mathematics developed for purely aesthetic reasons would mesh perfectly with what engineers or chromosomes do when they want to make a mess."