 |
|
 |
Card Shuffling |
 |
|
| ||||||
How to Win at Poker, and Other Science LessonsIf scientific reasoning were limited to the logical processes of arithmetic, we should not get very far in our understanding of the physical world. One might as well attempt to grasp the game of poker entirely by the use of the mathematics of probability. - Vannevar Bush
The mathematics of card shuffling is not just of interest to inveterate gamblers. It also has important applications in the sciences. 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 every 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. If 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 move the ace of spades from the top card to the 13th takes two inshuffles followed by two outshuffles. There is an intriguingly simple procedure for working out the necessary manipulations. Write down the places by which you would like the ace to move - in this case, 12. Then, write the number in its binary format (that is, using only 0s and 1s): for 12, this is 1100. This tells you how to shuffle: inshuffles are represented by 1s, 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 formula. 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 order does obey a simple rule. The problem is that one of the variables in the rule cannot be known in advance. So the only way 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 (that is, if the pack has 4, 8, 16, or 32 cards, and so on). Then, the number of outshuffles 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 case of 52 cards, the number of outshuffles needed is eight (28 equals 256, and 256 divided by 51 has a remainder of one). But for all pack sizes that are not powers of two, x cannot be calculated, and the number of outshuffles required 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 sometimes refer to "perfect-shuffle networks" - networks that look as if they are busily engaged in perfect shuffles. For example, if a parallel computer network consists of an array of simple processors acting in tandem, the way that it manipulates numbers looks remarkably like a pack of cards being shuffled perfectly over and over again. Mixing ItFortunately for honest card players, few people are capable of doing even one perfect shuffle; perhaps only 30 people in the world can reliably do eight in under a minute (the sort of speed necessary for 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 positions 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 1067.) According to Persi Diaconis, a magician-turned-mathematician at Harvard University (but currently visiting Cornell), shuffling with "riffle" shuffles - that is, cutting the pack and then dropping cards from each side, but not interleaving them perfectly - is highly effective at mixing up cards. After seven shuffles, the pack is close to being random. In contrast, shuffling overhand - that is, dropping little clumps of cards on to the back of the pack - is ridiculously ineffective. The pack will not be random 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 Saloff-Coste, David Bayer, Ron Graham (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 suddenly becomes random. The presence of this cut-off turns out to be important. Card shuffling, when imperfect, 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 only 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 becomes random. When the drunkard first sets off from the pub, he is not immediately likely 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 shuffling before the cards are mixed up. With the advent of powerful computers, which make big random simulations much easier, Markov chains have become popular in fields from statistics to biology. Most simulations start at some fixed position, but eventually reach an equilibrium state of randomness. But it is often important 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 random after a large number of steps - for example, how likely the drunk is to be anywhere after he has taken lm 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 starting 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 instance, 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 riffle shuffles are enough to mix up a pack of cards. Source: The Economist 12 October 1996
-------- Original Message -------- I found the 2 paragraphs (#7 and 8 perhaps) in the first article about determining the number of perfect outshuffles that will return a pack to its original order to be a bit misleading or at least confusing. The first of the paragraphs starts with:
While I may have peculiar tendencies in my usage, I don't like saying "cannot be known in advance". I, for example, DID know in advance that x=8 for a pack of 52 cards. I'm not sure offhand how I would suggest re-wording it. The next sentence, however, says: So the only way to work out the number of perfect shuffles needed to return a pack to its original order is to do them. Which is utterly absurd. It's much easier to simulate the shuffles than do them, and far easier still to just calculate y = 2x modulo (c-1) (where c = # of cards in the deck) for x = 1,2,3,... until you find that x that makes y=1. I would change that sentence to something like:
(if that is indeed the case). I like your description of the math involved, except for the last sentence. It has been a while since I was a math major, so maybe saying "x cannot be calculated" is appropriate, but I would be inclined to say something like "x cannot be easily calculated" or "there is no known formula that will calculate x" (and are you confident there has been no development in number theory along these lines?). Some mention of "brute force methods" (such as the one I specify below) might be worthwhile. Concluding by saying "the number of outshuffles ... cannot be worked out" is what really prompted me to respond because the math you supplied virtually defines an algorithm for working out what x will be. c = 52 (or whatever) * perfect outshuffles only work on packs with an even number of cards. * z = c - 1 I suspect, but don't know if there is a proof that this algorithm is guaranteed to terminate for all even c. Placing an upper bound on the size of x could be an interesting problem. At any rate, rather than ending with "cannot be worked out" you could just leave it with "no known formula" or some mention of brute force (feel free to use or adapt the obvious algorithm above). The site looks pretty interesting (how can I fail to like something that mentions Diaconis, the Trefethen's and tons of other random and non random subjects ;), and sorry for my ramblings ... I think really need to return to grad school. Bill L.
Shuffling: What's the Deal?by Philip Ball How many times do you really need to shuffle that deck of cards to rule out any chance of dodgy dealing? Two mathematicians hit the headlines in 1990 when they claimed that it took seven shuffles to make a pack of cards fully random, with no vestige of its original card order. Now comes a challenge to that claim. Five shuffles will almost do the job of randomisation, and six will make it certain, according to a paper in the Proceedings of the Royal Society*. It all depends on how you define "random", say Nick Trefethen and Lloyd Trefethen, respectively of Oxford University, UK, and Tufts University in Massachusetts in the US. The magic number of seven shuffles was proposed by David Bayer and Persi Diaconis in the USA, who considered how shuffling affected a quantity called the "total variation norm." This is a complicated measure of how effectively an ingenious gambler could be expected to win bets that the arrangement of cards in the deck was not completely arbitrary. Bayer and Diaconis chose to define randomness in this way because they were interested in how shuffling might affect play in casinos. Some professional card players will go to any lengths to exploit an element of non-randomness in a card deck. Most casino dealers shuffle between two and four times - which, according to Bayer and Diaconis, was nowhere near enough to lose all trace of the starting configuration of the pack. In fact, they claimed that there is virtually no true randomisation, as they defined it, until the 5th shuffle. Only after the 7th, they said, does their measure of "orderliness" of the deck fall below half the initial value - enough to consider the pack well mixed. Diaconis, himself a card magician, realised that astute card players could capitalise on this. He said that in his experience, shuffling seven times was almost unheard of in casinos. And he once spotted how bridge players in a New York club could anticipate the order of a deck shuffled four times between each hand. But the Trefethens say that the total variation norm, while a respectable measure of randomness, is not the only way to define it. They have instead considered a pack of cards as a package of information - a definition that stems from early work in telecommunications. If one knows the complete order of the pack, one has all the relevant information about it. If the pack is then shuffled until it is truly random, this information is reduced to zero - one has no idea where any particular card is. But how quickly does this information fall to zero? The researchers simulated shuffling on a computer, using the same idealised kind of riffle shuffle as Bayer and Diaconis, in which the pack is divided roughly in two and the cards are dropped on top of one another more or less alternately from each half. They found that, according to their definition of the "information" remaining about the order of the cards, the randomness accumulates steadily right from the first shuffle, and is virtually complete by the 6th. Even four shuffles does a fair job of reducing the "information content" of the pack. So which answer is correct: seven shuffles or six, or maybe just five? Even experts will dispute the significance of the two different measures of "randomness" in the pack. As far as card sharps are concerned, the differences will probably depend on what game one is playing. But it would be an extraordinary gambler indeed who could make money on the difference between 6 and 7 shuffles. References*Trefethen, L N & Trefethen, L M "How Many Shuffles to Randomise a Deck of Cards?" Proceedings of the Royal Society London A 456, 2561 - 2568 (2000) Source: www.nature.com 4 October 2000 © Nature News Service / Macmillan Magazines Ltd 2001
Clicking the "Next" button below will take you to Tells: The Fine Art of Losing at Poker. Clicking the "Up" button takes you to
the Table of Contents for this section where you can view thumbnails of Andrew Jones' curious deck of art cards. |
|
|
