When to stop shuffling depends on the game

By Julie Rehmeyer

Web edition: November 7, 2008

Enlarge

PRISONERS' CODE

ENLARGE | Stanford University researchers used mathematics to break coded messages prisoners were sending to each other. To find out what this note says, read the team's paper.

Credit:

Here’s the rule: To assure cards get sufficiently mixed up, shuffle a deck about seven times. Mathematician, magician and card shark Persi Diaconis of Stanford University, along with David Bayer of Columbia University, created shock waves in Las Vegas when he figured that out back in 1992. Most dealers had been shuffling much less.

But now Diaconis and his colleagues are issuing an update. When dealing many gambling games, like blackjack, about four shuffles are enough. The reason for the lower number is that many games require randomness for only a few specific aspects of the cards, not all. In blackjack, for example, suits don’t matter. Diaconis and his collaborators extended the earlier analysis to account for these variations.

Gamblers and casinos aren’t the only ones who will benefit. One the most useful tools for applied mathematicians — the Monte Carlo simulation — was inspired by the games of chance that are main attractions in Monte Carlo, Monaco. The new card-shuffling results apply directly to this method, promising to save mathematicians computer time.

Shuffling starts by cutting the deck roughly in half. During the shuffling, a few cards fall from one side, then a few from the other. Diaconis, Sami Assaf of the Massachusetts Institute of Technology and K. Soundararajan of Stanford University made the same assumption Diaconis and his collaborator Dave Bayer made back in 1992, that the cards are more likely to fall from the larger stack — an assumption borne out in real life.

Assaf started by using a very small deck, just four cards, and played with it a lot. Then she tried five, then six. From her experiments, she guessed a formula for how mixed the cards were, for whatever property she cared about. Then she worked out a proof.

The formulas she generated, though, were a mess. “We couldn’t actually calculate them,” she says. “We would have had to run the computer for 64 years or something like that.”

So she took each messy, complicated formula to Diaconis and Soundarajan, and for each they found a simple, easy-to-compute equation that approximated it. “We found a beautiful simple pattern,” Diaconis says. “There’s no reason this problem should have a nice answer. I’m not a religious person, but this is as close as I get.”

Previous researchers, specifically Mark Conger and Divakar Viswanath of the University of Michigan, had used computer simulations to work out some of these results. What makes the new approach from Diaconis and his colleagues stand out is that it can be applied to many different card games, using any number of cards. Even better, it can be used for situations far removed from cards, like Markov Chain Monte Carlo simulations, a technique that has revolutionized applied mathematics over the past few decades.

Markov Chain Monte Carlo simulations harness the power of randomness to solve all kinds of problems that don’t seem random at all. For example, prison officials once asked other mathematicians at Stanford for help decoding a collection of messages. The mathematicians guessed it had been made with a simple substitution cipher, where each symbol corresponded to a letter of the alphabet. The easiest way to solve substitution ciphers is by associating the most frequently used symbol with the most frequently used letter in English (e), the next most frequently used symbol with the next most frequently used letter (t), an so on. But that method failed.

The mathematicians then moved to the next level of sophistication, looking at the frequency of pairs of letters. They downloaded a copy of War and Peace and used it to build a table, showing the frequency with which one letter follows another. This table had 26 columns and 26 rows, and 26 times 26 equals far too many for deciphering by hand.

So the mathematicians used a Markov Chain Monte Carlo simulation. They built a simple program that chose a random letter to associate with each symbol. It then decoded the message using that substitution cipher and calculated how probable it was that the resulting pairs of letters in the decoded message would follow one another. It repeated the process with another random substitution cipher. If the new one was more probable, it picked it. If not, it usually kept the original one, but occasionally switched to the new one. After a thousand or so iterations, it had decoded the message — even though the message was written in a mix of English, Spanish and prison jargon.

One of the tricks is recognizing when the simulation can stop, and Diaconis’ new result for shuffling can help with that. Choosing a new random solution in a Markov Chain Monte Carlo simulation is a bit like a shuffle of the cards. The methods Diaconis has developed to recognize when a dealer can safely stop shuffling the cards can also tell when the computer can stop running the simulation.

“We’re all enthusiastic,” Diaconis says, “because you can describe it to your mom, the math is hard, and the results are interesting.”