7 Shuffles is Enough

A famous result by our mathemagician Persi Diaconis: 7 shuffles is enough. Put it in everyday words, to randomize one set of Poker cards, you need to (Riffle) shuffle at least 7 times.

*Side note: according to this lecture notes, the interpretation is not correct. To completely randomize the deck, you need 11 or more. 7 is just a cutoff point for the process of randomization.

riffle_shuffle

I found this lecture notes online that rephrases this result and proof in a very approachable way. Here’s a brief summary:

Split the deck of cards into a pile with m cards and another with 52-m cards. Riffle shuffle is defined rigorously as a process where during each step, the card on the left drops with prob \frac{a}{a+b}, and the card on the right drops with prob \frac{b}{a+b}, a is the number left on the left.

Then define reverse shuffling by first assigning bits to cards uniformly randomly, and then pulling 0’s to the top preserving order.

By the reverse shuffling definition, we can compute the strong stationary time of Riffle shuffle.

Note.
For a deck of 52 cards we can calculate the deviation distance after
t=1,…10 Riffle shuffles. The following table can be found in [7].
t       1       2      3    4    5       6       7       8      9     10
dv(t)1.0 1.0 1.0 1.0 0.92 0.61 0.33 0.16 0.8 0.04
We notice that before the 7th step the deviation distance is not changing much. However, at the 7th shuffle it almost halves and it continues getting half of its previous amount after each single shuffle. Therefore, time 7 can be considered as the “cut off” point. This might be the reason that the result has been famous as “seven shuffles is enough”. However, we definitely know that the distribution after 7 shuffles is still far from being uniform. Also, note that there are 11 steps needed if you consider exact mixing.
Still, I’m too lazy to shuffle more than 3 times for a Poker round.
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s