Monday, March 03, 2014
In Which We Discover That Every Shuffle Of A Deck of Cards Is Undiscovered Country
by Jonathan Kujawa
A few years ago I decided I should learn a few card tricks. Like tying a necktie, eating with chopsticks, or building a fire, it seemed like the sort of thing everyone should have in their skill-set. As a person with mediocre dexterity I need tricks which don't depend on slight-of-hand. Fortunately for me the combinations, symmetries, and probabilities of playing cards means there is a rich tradition of card tricks which depend on math more than skill. That's the sort of trick even I can do.
My current favorite is Colm Mulcahy's Ice Cream Flavor Trick. Mulcahy is a mathematician and magician at Spellman College. He has written numerous articles and books on math and card tricks. You can find links to many of them on his homepage.
While idly shuffling cards I stopped and wondered: what is the chance that a deck of cards has ever occurred before in exactly the same order as the ones in my hand? 
On the one hand, I knew that there are many, many, many possible orderings of a 52 card deck. On the other hand, there are millions of decks of cards being shuffled all the time. Just imagine all the shuffling in Vegas alone!
The answer is truly startling! I was surprised and delighted by the how incredibly likely my deck of cards had never occurred before. Let's do the numbers together.
First, how many orderings are there for 52 card deck?
Well, let's say we have an ordered deck and work our way from top to bottom counting the possibilities. There are 52 possibilities for the top card. Whatever that is, there are 51 possibilities for the second card (because it can't be whatever the top card was). Whatever the top two cards are, there are 50 possibilities for the third card (because it can't be either of the two top cards). And so on. At the very end there is only one possibility for the last card as the other 51 are already accounted for.
To get the total number of possible orderings, we should multiple 52, 51, 50, ...., 3, 2, 1 all together (to see that this is right, it's easier to try it first with a 3 or 4 card deck). The shorthand for this product is 52! (read fifty-two factorial). According to wolframalpha, the number of different orderings of a 52 card deck is:
This is round about 80 vigintillion. That's 80 with 63 zeros after it. By way of comparison, that is way, way more than the number of atoms which make up the Sun. A big number by anyone's measure!
Now, how many different orderings have occurred in the history of card shuffling? There is no way to know, of course, but we can estimate. To be on the safe side, at every step we'll err on the side of overestimating.
- People have been playing cards for a few thousand years. To be safe, let's say 10,000 years.
- There are about seven billion people on the Earth. Let's say that now and in the past there have always been 10,000,000,000 people.
- There are 31,536,000 seconds in a year. Let's say there are 50,000,000 seconds in a year.
Now, imagine that from the moment cards were invented everyone devoted every second of every day to shuffling decks of cards. To count the number of orderings which have occurred, we multiply these numbers. That is, the number of orderings we've seen so far is at most:
That's 5 sextillion; a 5 with 21 zeros after it. That's a huge number - but it's way, way smaller than the 80 vigintillion possible orderings.
In fact, to go back to my original question, the odds that my well mixed deck of cards has occurred before is (5,000,000,000,000,000,000,000)/(52!). Computing this on wolframalpha, we see that's comparable to the odds of picking one out of all the atoms in the earth.
Here's another way to put it in perspective. Let's compare the likelihood of my deck of cards having previously occurred with winning the Powerball lottery. The odds of winning the grand prize in the Powerball lottery is 1 in 175,223,510. A quick calculation shows that it is more likely that I will win the next five Powerball drawings in a row!
 By well mixed, I mean the cards have been shuffled enough so that every possible ordering is equally likely. By shuffle I'm thinking of the usual riffle shuffle used by most card players. It's not hard to see that certain orderings can't possibly happen after only one shuffle. For example, if you think about the card which is at the bottom of your deck, after one shuffle it is still somewhere in the bottom half of your deck. So definitely not all orderings are equally likely after one shuffle. And indeed there are card tricks which depend upon the fact that even after three shuffles a deck is still not well mixed!
So how many shuffles does it take to ensure a deck is well mixed? Mathemagician Persi Diaconis and Dave Bayer answer that question in a delightful paper entitled "Trailing the dovetail shuffle to its lair" which is available here. In it they compute how close a deck of cards is to well mixed after m shuffles. Here is the table from their paper where they compute the "distance" between a deck shuffled m times (Qm in the table) and a well mixed deck (U in the table). Remarkably, their work shows that while the first few shuffles of a deck aren't very random, you converge to a well mixed deck very rapidly thereafter. You can also read about their work here.
The upshot is that seven shuffles is probably enough to consider the deck well mixed for every day card play, and 15 shuffles is plenty if you're playing for serious money.
Posted by Jon Kujawa at 12:50 AM | Permalink