Card Shuffling: You’re Not Done Yet

When playing games involving a deck of cards, I am sometimes told that I take too long to shuffle the deck.  This is due in part to the fact that I simply do not shuffle very well, and the extra fumbling takes time.  But I also tend to shuffle the deck more times than might seem typical, reasonable, or necessary– usually 8 or 9 riffle shuffles if I can get away with it.

There is a lot of interesting mathematics involved in shuffling cards.  I will not try to re-hash all of the many applications and beautiful results here; see the references at the end of this post for some great survey reading on the subject.  Instead, I will just point out a few specific ideas that are interesting and/or new to me.

First, my interest in card shuffling was renewed recently via a rather roundabout path between related problems, beginning with “cold hit” DNA profiling, progressing from there to the birthday problem, and ending with the question of whether it is likely or not that there have ever, in the history of playing cards as we know them today, been two completely shuffled yet identically arranged decks of cards.  I think this would be a great exercise for students, particularly because of the interesting end result, namely that it is extremely likely that no two completely shuffled decks have been the same.

Of course, this raises further questions about the assumptions implied in the problem, in particular what “completely shuffled” means.  Basically, we would like the probability distribution on the set of all possible deck arrangements to be uniform… or as nearly uniform as possible.  This leads naturally to the widely cited, perhaps even “popular” anecdote due to Bayer and Diaconis, that seven riffle shuffles of a 52-card deck are needed to randomize the deck (references 1-3).

This result involves some very elegant mathematics, from the random modeling of the riffle shuffle to the choice of metric for distance between probability distributions.  More precisely, the Bayer-Diaconis result is that total variation distance from the uniform distribution first drops below 0.5 after seven GSR riffle shuffles, so named after Gilbert, Shannon, and Reeds, who first studied them.

(Last week I read a paper by Trefethen (reference 4) that considers information-theoretic entropy as another measure of randomness.  Although I do not read their conclusions quite this way, the paper seems to be cited as suggesting that only five or at most six shuffles are sufficient.  I don’t quite agree with this, as will be shown below.)

I think it is useful to consider relatively simple ways to explain and justify repeated riffle shuffling, whether to your family or friends across the card table, or to students in the classroom.  Following is an outline of three interesting arguments showing that you need at least four, five, and six riffle shuffles, respectively, at a minimum, to randomize a deck of 52 cards.

First, three shuffles are definitely not enough: Bayer and Diaconis describe a very cool card trick called “Premo,” discovered by Charles Jordan (reference 3).  The magician hands a deck to the spectator, and tells the spectator to riffle shuffle the deck three times, then cut the deck.  The spectator is then instructed to look at and remember the top card, insert it randomly into the deck, and give the deck a final cut.  The magician takes the deck and fans it on the table, and after looking at the cards for a few moments, announces the spectator’s chosen card.

This trick is surprisingly easy to learn, and with some practice I have gotten much faster at identifying the chosen card.  What is interesting is why and how the trick works… and when it doesn’t.  I have run some computer simulations of the trick, and although I can reproduce Bayer and Diaconis’s results, the probability that the trick works seems to be very sensitive to how the cuts and random insertion of the chosen card are modeled (e.g., uniformly, binomially, etc.).  More analysis is warranted here.  [Edit: That further analysis turned out to be pretty interesting.]

Four shuffles are not enough, either.  Consider weakening the requirements a bit, from demanding that all possible arrangements of cards be approximately equally likely, to simply ensuring that all arrangements are possible.  That is, how many riffle shuffles are needed to have any chance of generating each of the 52! possible arrangements of the deck?  If there are different single riffle shuffles, then is a lower bound on the required number of shuffles.  We can associate every possible riffle shuffle with a binary sequence of length 52, where the number of zeros indicates the position of the cut, and the pattern of zeros and ones indicates the interleaving of cards from the top and bottom packets, respectively.  Thus, , yielding a lower bound of at least five riffle shuffles.

Finally, we can refine the above argument a bit by considering the number of shuffles required to reach a particular permutation of cards.  It turns out that a reversal of the order of cards is the “hardest” permutation to reach, by considering the number of “rising sequences” in a permutation (see references 1,2).  Since a single shuffle at most doubles the number of rising sequences (this takes some work to show), we need at least shuffles to realize the 52 rising sequences in the permutation that reverses the deck.

In summary, the above arguments show that you need at least six riffle shuffles just to have a chance of realizing all possible arrangements of the deck.  Throw in just one more shuffle “for good measure” of randomness, and the anecdotal seven shuffles seems like a reasonable guide.

References:

1. Diaconis, Assaf, S. and Soundararajan, Riffle shuffles of a deck with repeated cards. K. DMTCS Proceedings, 21st International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2009), 0(1):89-102. [PDF]
2. Diaconis, Mathematical Developments from the Analysis of Riffle-Shuffling. In A. Fuanou, M. Liebeck (eds.) Groups Combinatorics and Geometry, pp.73-97, World Scientific, N.J. (2003). [PDF]
3. Diaconis and D. Bayer, Trailing the Dovetail Shuffle to its Lair. Ann. Appl. Prob., 2(2):294-313. (1992) [PDF]
4. Trefethen, L. N. and Trefethen, L. M., How many shuffles to randomize a deck of cards? Proceedings of the Royal Society, Series A 456 (2002): 2561–2568, doi:10.1098/rspa.2000.0625