You are the dealer. You know that the top five cards are the ace,king, queen, jack, and ten of spades. If you are playing poker with three other people, how can you deal these cards to yourself?
The most elegant way is to do two perfect shuffles. A perfect shuffle-- when the pack is cut exactly in half and the cards are then dropped one at a time from alternate sides until the two halves are interleaved evenly-- is the crooked gambler's dream.After one perfect shuffle, the five cards previously at the top of the deck will now be ev- ery second card; after two such shuffles, they will be every fourth card.
However, you must remember to do what magicians call `` inshuffles''. That is, if you cut the cards and pick up the top half of the pack in your right hand, you must start dropping the cards from the right-hand side. This way, the top card will become the second card, and then the fourth. tf you make a mistake and do ``outshuffles'', starting instead from the left-hand side, the top card will stay on top, and you will deal the royal flush to the person lucky enough to be sitting to your left.
Perfect shuffles are one way to manipulate cards: to remove the ace of spades from the top card to the thirteenth takes two inshuffles followed by two outshuffles. There is an intriguingly simple procedure for working out the necessary manipula- tions. Write down the places by which you would like tile ace to move-- in this case, 12. Then, write the number in its binary format (i.e., using only 0s and 1s): for 12, this is 1100. This tells you how to shuffle: inshuffles are represented by1s, outshuffles by 0s.
Even better, after eight outshuffles in a row the pack returns to the order it started off in (it takes 52 inshuffles to achieve the same result). Strangely, this rule only applies for a pack of 52 cards. The cyclical behaviour of a pack of 48 cards (used for games such as bezique and pinochle) or of 104 cards is different. Moreover, it cannot be predicted using any mathematical for- mula. Although this sounds like a simple problem, it is in fact an example of a deeply puzzling question in number theory.
The number of outshuffles required to restore any pack of cards to its original or- der does obey a simple rule.The problem is that one of the variables in the rule cannot be known in advance. So the only wav to work out the number of perfect shuffles needed to return a pack to its original order is to do them. There is an exception: when the number of cards in a pack is exactly equal to two raised to the power of a whole number (i.e., if the pack has 4, 8, 16, or 32 cards, and so on). Then, the number of out- shuffles is the same as the exponent: for a pack of four cards it takes two outshuffles, for a pack of 32 cards it takes five.
More generally, it turns out that the number of outshuffles needed to get a pack back to its starting point is the smallest power of two-call it x-- such that two raised to the power of x and then divided by a figure that is one less than the number of cards in the pack leaves a remainder of one. For example, in the caseof 52 cards, the number of outshuffles needed is eight (2^8 equals 256, and 256 divided by 51 has a re- mainder of one). But for all pack sizes that are not powers of two, x cannot be calcu- lated, and the number of outshuffles re- quired to return the cards to their original order cannot be worked out.
The behaviour of perfect shuffles is not just of interest to magicians and card sharps. Engineers and physicists some- times refer to ``perfect-shuffle networks''-- networks that look as if they are busily en- gaged in perfect shuffles. For example, if a parallel computer network consists of an array ot simple processors acting in tandem, the way that it manipulates mimhers looks remarkably like a pack of cards beirig shuffled perfectly over and over again.
Mixing it
Fortunately for honest card players, few people are capable of doing even one per- fect shuffle; perhaps only 30 people in the world can reliably do eight in under a minute (the sort of speed necessafy tor it not to be obvious that something peculiar is going on). So when most people shuffle a deck, they mix up the cards. But how long does it take before the deck is really mixed?
For mathematicians and statisticians, a pack of cards is randomly mixed when every card is equally likely to be at all posi- tions in the deck. (A pack of 52 cards has 52- factorial possible arrangements, or 52 multiplied by 51 multiplied by 50. . . and so on all the way down to one. This is a large number: 8.065 times 10^67.)
According to Persi Diaconis, a magi- cian-turned-mathematician at Harvard University (but currently visiting Cornell), shuffling with ``riffle'' shuffles-- i.e., cutting the pack and then dropping cards from each side, but not interleaving them per- fectly-- is highly effective at mixing up cards. After seven shuffles, the pack is close to being random. In contrast, shuffling overhand--i.e., dropping little clumps of cards onto the back of the pack-- is ridicu- lously ineffective. The pack will not be ran- dom until the procedure has been repeated 2,500 times.
Moreover, Dr Diaconis (who can do eight perfect shuffles in a row) and his colleagues-Laurent SaloffCoste, David sayer, Kon C.rall.ltil (who also works on the mathematics of juggling) and William Kantor-- have recently discovered an even more bizarre phenomenon: in some systems, the switch to randomness is abrupt. In other words, after six riffle shuffles, a pack is still visibly ordered. But after the seventh, it sud- denly becomes random.
The presence of this cut-off turns out to be important. Card shuffling, when imper- fect, is a good example of something called a ``Markov chain''. This is a random process in which the future depends only on the present, not on the past. For instance, what a shuffle does to a pack of cards depends only on the order they are in before that shuffle, not on how they got to be in that order. Or think of a drunkard staggering about. His next step depends onIy on where he is now, not on where he came from.
But at the start of a random process, it takes a while before a system actually be- comes random. When the drunkard first sets off from the pub, he is not immediately likelv to be anywhere between the pub and his house: he will be close to the pub. Likewise with card shuffling. Buy a new pack of cards, and it obviously takes a bit of siluf- fling before the cards are mixed up.
With the advent of powerful comput- ers, which make big random simulations much easier, Markov chains have become popular in fields from statistics to biology. Most simulations start at some fixed posi- tion, but eventually reach an equilibrium state of randomness. But it is often impor- tant to know how long this takes. Otherwise, the results of the model may be affected by the state that the system started out in. In the case of a pack of cards, without enough shuffles (particularly if shuffling overhand) the current order will still partly depend on the original one.
Mathematicians have long been able to predict how close a system is to being ran- dom after a large number of steps-- for example, how likely the drunk is to be any- where after he has taken zm steps, or how likely a pack of cards is to be mixed after 20,000 shuffles. But this says nothing about how long it takes to become random from a fixed ctal th point.
This is where the cut-off comes in. Dr Diaconis and his colleagues have worked out methods for identifying which systems have such sudden breaks-- these can drastically speed up the approach to randomness-- and for working out where they are.
Systems that do not have a cut-off-the drunkard's walk is one-will approach a state of randomness gradually. Some of them can take a long time to do so. For in- stance, if the space the drunkard is walking in is large, it will be a long time before he is equally likely to be anywhere within it.
Dr Diaconis argues that this information is crucial. For the users of Markov models, it can prevent embarrassing errors. For everybody else, perhaps it is just handy to know that seven imperfect rimc shuffles are enough to mix up a pack of cards.