|Ivars Peterson's MathTrek|
October 16, 2000
About 30 years ago, tournament bridge players started using computer-shuffled rather than hand-shuffled decks. Almost immediately, there was an outcry protesting the apparently wild fluctuations in the distribution of cards of different suits in computer-dealt hands.
However, the problem lay not in the computer but with human expectations. Subsequent research showed that hands in which suits are evenly distributed, that is, hands with four cards of one suit and three of each of the other suits, are actually more common in games in which people do the shuffling than they should be according to theory.
The reason for such a pattern is that cards during bridge play tend to clump together in groups of four of the same suit. Careless shuffling doesn't do enough to break up the groups, and when the cards are dealt out, the four players get a fairly even distribution of suits.
In fact, before the advent of computer shuffling, the intuition of bridge players had been shaped by generations of improperly shuffled cards. A close look at books published in the past reveals that some experts had figured out that cards generally aren't shuffled well and had developed strategies that took such quirks into account. When computer shuffling was introduced, many of these strategies had to be revised.
How many times must a deck of 52 cards be shuffled before the cards are randomly distributed? It turns out that trying to answer this question raises a number of subtle issues concerning both card shuffling and various measures of randomness.
In the May 1986 American Mathematical Monthly, statisticians David Aldous of the University of California, Berkeley, and Persi Diaconis of Stanford University argued that roughly seven riffle shuffles are sufficient to achieve an acceptable degree of disorder in a deck of 52 cards. (In a riffle shuffle, the deck is cut into two, possibly unequal packets, and the two packets are then raggedly interleaved.) Diaconis and David Bayer of Columbia University later refined this result.
With five or fewer shuffles, the original order of the standard deck is strongly in evidence. With more than seven shuffles, the original order has virtually disappeared. So, although no finite number of shuffles will ever make anything completely random, it doesnt take long to get close enough for practical purposes.
Such abrupt transitions from order to randomness show up in a variety of mixing processes. You might ponder the same sort of behavior in your own kitchen when stirring together white flour and cinnamon. At first, you see thick streaks as the ingredients mingle. After a few more strokes, the whole mixtures suddenly smooths to a tan color.
Whether as many as seven shuffles are really necessary, however, depends on how you define and measure randomness, say Nick Trefethen of the University of Oxford in England and Lloyd Trefethen of Tufts University in Medford, Mass. They now argue in the Proceedings of the Royal Society that five shuffles would do a reasonable job of randomization and six would make it practically certain the cards are thoroughly mixed.
To determine how many shuffles would adequately randomize a deck, Diaconis and Bayer worked with a statistical measure known as the "total variation norm." This number quantifies the rate at which an ideal gambler could expect to make money, on average, if allowed to place bets against a fair house by taking advantage of any residual pattern among cards in a deck. In this model, the "total variation distance to randomness" falls below 0.5 after seven shuffles.
The Trefethens adopted an alternative definition of randomness--one rooted in the telecommunications industry. They considered a deck of cards as a packet of information.
If you know the location of every card in the deck, you have all the necessary information about the deck. If the deck is then shuffled until it is truly random, you end up with zero information about the card distribution. For the Trefethens, the issue was how quickly shuffling destroys information about the card distribution.
Technically, the researchers looked at a number that "quantifies the rate at which an infinitely competent coder could expect to transmit information, on average in the limit of infinitely long message lengths, if permitted to encode signals arbitrarily in shuffled decks of cards."
Using computer simulations of riffle shuffles, the Trefethens found that, according to their measure of the information left about the card distribution, the amount of information (degree of order) decreases steadily with each shuffle, reaching virtually zero information with the sixth shuffle and staying there with each subsequent shuffle.
"It is not obvious, even to experts, what the full significance is of the distinction between our two measures of randomness," the researchers conclude. Which measure of randomization is relevant for card players may even depend on the types of games they play.
What should be clear, however, to the everyday player is that, no matter which model is relevant, just three lackadaisical shuffles isn't enough.
Copyright 2000 by Ivars Peterson
Aldous, D., and P. Diaconis. 1986. Shuffling cards and stopping times. American Mathematical Monthly 93(May):333.
Ball, P. 2000. Shuffling: What's the deal? Nature Science Update (Oct. 4). Available at http://helix.nature.com/nsu/001005/001005-8.html.
Bayer, D., and P. Diaconis. 1992. Trailing the dovetail shuffle to its lair. Annals of Applied Probability 2:294.
Berger, P. 1973. On the distribution of hand patterns in bridge: Man-dealt versus computer-dealt. Canadian Journal of Statistics 1:261.
Diaconis, P. 1996. The cutoff phenomenon in finite Markov chains. Proceedings of the National Academy of Sciences 93(February):1659.
Folger, T. 1991. Shuffling into hyperspace. Discover (January):66.
Keller, J.B. 1995. How many shuffles to mix a deck? SIAM Review 37(March):88.
Kolata, G. 1990. In shuffling cards, 7 is winning number. New York Times (Jan. 9).
______. 1985. Prestidigitator of digits. Science 85 6(April):67.
Peterson, I. 1990. Islands of Truth: A Mathematical Mystery Cruise. New York: W.H. Freeman.
______. 1984. Mathematical shuffling. Science News 125(March 31):202.
Trefethen, L.N., and L.M. Trefethen. 2000. How many shuffles to randomize a deck of cards? Proceedings of the Royal Society, London A 456(Oct. 8):2561. Abstract available at http://www.pubs.royalsoc.ac.uk/proc_maths/abstracts/2002.htm.
A brief outline of the mathematics of card shuffling can be found at http://mathworld.wolfram.com/Shuffle.html.
Comments are welcome. Please send messages to Ivars Peterson at email@example.com.
Ivars Peterson is the mathematics/computer writer and online editor at Science News (http://www.sciencenews.org). He is the author of The Mathematical Tourist, Islands of Truth, Newton's Clock, Fatal Defect, and The Jungles of Randomness. He also writes for the children's magazine Muse (http://www.musemag.com) and is working on a book about math and art.
Ivars Peterson will present "A Kaleidoscope of Mathematics and Art" at the Joint Mathematics Meetings in New Orleans on Jan. 13, 2001, at 10:05 a.m.