You may have heard the rule that you need to shuffle a deck of cards at least 7 times in order for it to be truly mixed up. (At least I have, but my parents are mathematicians so that might just be me). Regardless, this rule should raise a few questions:
- What do we mean by shuffle? Your little brother might shuffle cards by throwing them on the ground and mixing them up, but surely that isn’t what we mean here.
- What do we mean by truly mixed up?
- Where the heck does the number 7 come from?
It turns out these questions aren’t so simple — there’s an entire paper written about this — but we’ll see what sense we can make of them.
The authors of the paper, Bayer and Diaconis, mathematically model what we think of as a conventional shuffle: splitting the deck roughly in half and riffling the cards together. Notice that if you shuffle several times, the way you split the cards into two piles and the way you riffle them together will probably be different each time. This introduces an element of chance!
The authors choose to model splitting the deck in two with the binomial distribution, meaning the most likely split is half and half, and we’re likelier to have splits close to half and half than far.
Once we have our two piles, riffling the cards together is the same as taking a card from the top of either pile until we have one big pile. The authors make the probability of taking the next card from each pile proportional to the size of that pile. If there are A cards in one pile and B cards in the other, the probability that the next card comes from the pile with A cards is A/(A+B). This is called the Gilbert-Shannon-Reeds model of shuffling.
We now have a mathematical way of looking at shuffling! It might not 100% align with real-life shuffling, but it should seem pretty close.
Ok, so when is the deck mixed up?
One requirement we might want to set is that the cards be in a different order after we shuffle them. If we’re playing Go Fish, we don’t want the cards already sorted by number. But wait! No matter how many times we shuffle, there’s still a chance, albeit small, that we end up in the exact same order we started in. Under this definition, we’d have to shuffle forever.
The same can be said for the requirement that the order after shuffling be sufficiently different (however we measure that) from the original order. Darn.
And even looking at two decks of cards, it’s hard to say which is more mixed up, just like it’s hard to say whether your poker hand is more random than an opponent’s.
Let’s take a step back and think about what we want to achieve by shuffling. Shuffling serves as a way to reset the deck and start fresh. In other words, we don’t want the order before shuffling to help anyone predict the order after shuffling. This is equivalent to ensuring that the deck is equally likely to end up in each possible ordering. We call this the uniform distribution.
Now I know how to shuffle and what I want to achieve. How long will this take?
We can start off with a simple example to see why one shuffle isn’t enough.
In the example above, we start with a deck of 3 cards. There are 4 possible splits into left/right decks: 3 cards/0 cards, 1/2, 2/1, and 0/3. In the 3/0 and 0/3 cases, the cards will trivially stay in the same order after riffling them together. The 1/2 (Split 1) and 2/1 (Split 2) cases are depicted above. Take a look at the final shuffled orders for each case. Notice anything?
Even with so few cards, there is no way to reverse the deck in one shuffle. And if one of the orderings isn’t possible, the cards definitely aren’t mixed up. We didn’t even need to use probability to see this!
Suppose that in the right pile, Card A comes directly before Card B. No matter how we riffle the cards together, Card B can never come before Card A, though there may be cards between them. Riffling the cards together preserves the ordering in each pile, so reversing the deck relies on the cut, when we separate the deck into two piles.
The above table shows how mixed up a deck of 52 cards is after 1 through 10 shuffles. Total variation distance measures how different shuffling cards m times is from the uniform distribution. More simply, a high total variation distance means the deck isn’t very mixed up, and a total variation distance of 0 would make a deck totally mixed up.
The total variation distance is still nonzero well after 7 shuffles, so what’s going on here? Since this is a real world problem, the authors are respectful of our time. To get a total variation distance of 0, we’d have to shuffle forever. That’s a long time! So how do we decide when to stop?
If we eyeball the graph, we can see that the total variation distance stays constant, decreases sharply, then begins to level out around 7. Since the total variation distance after 7 shuffles (.334) is fairly close to 0, and each additional shuffle helps us substantially less, we might as well call it a day after 7.
But why does the graph behave this way? Well, that’s where things start to get really complicated. If you’re interested in learning more, I’d recommend reading the original paper, which introduces other types of shuffles that they show are equivalent to the riffle shuffle, and uses concepts from all over math to tie everything together.
Based on “Trailing the Dovetail Shuffle to its Lair” by Bayer and Diaconis.