Shuffling Into Hyperspace

No matter how good a card player you are, you probably don't shuffle your cards enough, at least according to mathematicians Persi Diaconis of Harvard and David Bayer of Columbia. This past year they made headlines with their announcement of a mathematical proof that it takes at least seven riffle shuffles to thoroughly mix a deck of 52 cards. More than seven won't make much difference.

The problem had long stumped other mathematicians. A 52-card deck can be arranged in an enormous number of ways. Any of the 52 cards can be first in the deck, any of 51 can be second, and so on. The number of possible arrangements is 52 x 51 x 50 ... all the way down to 1. The resultant number, roughly 1068, is far larger than the number of seconds that have elapsed since the universe began. Trying to figure out how many shuffles it takes to make How each one of these arrangements deck equally likely, and to erase all influence of any previous arrangement, had proved an intractable task.

Bayer and Diaconis took an unusual approach: they did lots of fieldwork. They played cards. They haunted casinos. They even tape-recorded decks being shuffled, and analyzed the sound to see how the cards were interleaved. And in the end they found a simpler way of measuring the randomness of a deck.

As even an amateur cardplayer knows, you can tell a deck hasn't been thoroughly shuffled when a particular sequence of cards from one hand crops up in the next. To transform this intuition into a general measure of randomness, Diaconis and Bayer defined something called a rising sequence. If you number the cards in a deck from 1 to 52, and forget about the faces, a rising sequence is a sequence of consecutively numbered cards, such as 1, 2, 3 or 17, 18, 19, 20. The cards don't have to be next to each other to be part of the same rising in a deck, you start with the top card and then proceed toward the bottom, skipping over cards until you find the card numbered one higher. When you reach the bottom of the deck, the first rising sequence is over. The next one begins with the first card you skipped.

Now imagine that the deck starts out in perfectly consecutive order, with card number 1 at the top and card number 52 at the bottom. That deck has one rising sequence. if it is cut evenly into two stacks, one stack will contain cards numbered I through 26, the other cards 27 through 52. After the shuffle the deck will look something like this: 1, 27, 2, 28, 3, 29.... The shuffled deck has two intermixed rising sequences: 1, 2, 3 ... and 27, 28, 29.... With each shuffle, in fact, the number of rising sequences increases and the sequences get shorter. A thoroughly shuffled deck has 26 rising sequences, and any trace of the original order is gone.

How many shuffles does it take to get there? After watching countless card games, Diaconis and Bayer were convinced that seven was the magic number. Through educated guesswork, they came up with a formula for calculating the probability that a given number of shuffles would produce a given number of rising sequences. The formula predicts that seven shuffles will generate close to 26 rising sequences -- in other words, that seven shuffles will randomize the deck. "We were guided in our calculations by knowing what the right answer was," says Diaconis. "That is, we hoped we knew what the right answer was. Mathematics has a way of surprising you."

The researchers still had to prove that their formula was correct. That's when they made their second innovation: a geometric description of shuffling. "We had a real breakthrough," says Diaconis. "It wasn't just a matter of using bigger computers. We had a completely new way of looking at the problem."

The new method is abstract but visual: it uses a 52-dimensional hypercube to represent all possible arrangements of a 52-card deck. A point inside the hypercube represents the current state of the deck. Each axis corresponds to one card, and the position of the point along that axis corresponds to the card's position in the deck -- the further you go along the axis, the closer that card is to the top of the deck. Rank the point's 52 coordinates according to their magnitude, and you will have written down the sequence of the cards.

Each of the 1068 possible sequences is represented in the hypercube by an individual "volume element," within which the ranking of the coordinates does not change. If you can visualize a 52-dimensional volume element, you're not from planet Earth, but it's not hard to visualize in three dimensions-that is, for the case of a three-card deck. In that case the hypercube reduces to an ordinary cube with three axes, x, y, and z, that originate at one corner. The volume elements are six tetrahedrons that have in common the diagonal that cuts across the cube from the point of origin. Within each tetrahedron the ranking of the three coordinates -- say, x is greater than y, and y is greater than z -- doesn't change. Each tetrahedron corresponds to one of the six possible sequences of three cards.

Now go back to 52 cards, and to shuffling. In the hypercube model, shuffling corresponds to moving the point from one volume element to a different one. Diaconis and Bayer represent the process this way: first they stretch all 52 axes of the hypercube to twice their length, then they cut the doubled axes in half and mash each new half back into the old one. (The operation is similar to stretching and folding dough, which is why the researchers have dubbed it the baker's transformation.)

When the axes are doubled, the volume element containing the point is stretched to 252 times its size. It can then be divided into 252 new volume elements. All the new volume elements are carbon copies of elements in the original hypercube; they represent card arrangements that the deck can be put into by that shuffle. Some elements are copied more than once, reflecting the fact that a single arrangement of the deck can be arrived at by several different ways of cutting and interleaving the cards. And here's the key: when the axes are doubled, the point's coordinates are doubled, too. In the process the point can travel into any of the new volume elements, but then it inevitably gets mashed into the corresponding element of the original hypercube -- and the deck winds up in that arrangement of the cards -- when the axes are cut back to their original length.

To figure out the probability of the cards ending up in a particular arrangement, all you have to do is add up all the volume elements corresponding to that arrangement after the original volume element has been stretched. After one stretch, there are more copies of some elements than of others. What Diaconis and Bayer found is that you have to double the axes seven times (without cutting them back) before all 1068 of the original volume elements are represented almost equally-which is the same as saying you have to shuffle cards seven times before all 1068 theoretically possible arrangements of the deck become equally likely. "Once we had a geometric representation of shuffling," says Diaconis, "the problem boiled down to counting up volume elements."

Diaconis is tickled at the reaction his work has gotten. "The most you can usually hope for in mathematics," he says, "is the grudging acknowledgment of a few people who know what you're talking about. But shuffling cards seems to have captured people's attention."

Tim Folger, Discover Magazine 1990