While seven riffle shuffles are famously known to be enough to randomize a deck for practical card games, this problem illustrates that they do not produce a perfectly uniform mathematical distribution. In fact, the two distributions are still so different that in our setting it’s possible to tell them apart with virtual certainty – the problem would still be solvable if we required 100% of your answers to be correct.
Probably the simplest way to tell the two distributions apart is to track what happens to pairs of cards that were adjacent in the new deck order.
In a perfectly uniform shuffle, any two cards have an exactly 50%
chance of being in their original relative order (e.g., C
appearing anywhere before D). Since there are \(51\) adjacent pairs in a 52-card deck, the
expected number of preserved pairs per deck is exactly \(25.5\). Across \(1000\) decks, this expected total is \(25\,500\).
The Gilbert-Shannon-Reeds (GSR) riffle shuffle works by cutting the deck and interleaving the two halves. This inherently preserves the relative order of cards within each of those halves. Even after 7 iterations, the deck retains a measurable memory of its original state in the sense that the number of preserved pairs is still larger than it should be for a truly random permutation.
To gain a bit more intuition about why this happens, consider whether it’s possible that after five consecutive riffle shuffles the decks ends up completely reversed.
For a truly random shuffle we can compute not just the mean but also the variance of the number of preserved adjacent pairs. The calculation is simple, we just need to keep in mind that the 51 random events we’re interested in aren’t completely independent: if we have two consecutive pairs of cards \((i, i+1)\) and \((i+1, i+2)\), the events “\(i\) is before \(i+1\)” and “\(i+1\) is before \(i+2\)” are not independent. If we take this correctly into account, we’ll get that the variance for a single deck is exactly \(53/12\).
This means that for 1000 uniformly shuffled decks the number of preserved adjacent pairs has the mean of \(25\,500\) and the standard deviation of \(\sqrt{53000/12} \approx 66.458\).
We also know how to do the math for riffle shuffles. These results were first done and published by Dave Bayer and Persi Diakonis in 1992 and the popular shorthand about seven riffle shuffles comes from (somewhat over)simplifying the results shown in this particular paper.
Of course, in a contest we don’t have to do any math at all. Instead, we can simply run a million experiments of each type and use those to get a pretty good idea of the means and standard deviations for both types of randomness.
Either way, for the seven riffle shuffles distribution we’ll get that the mean number of preserved adjacent pairs in 1000 decks is roughly \(27\,900\) and this number has a standard deviation of slighly below 66.
Looking at the standard deviations is useful because it can tell us how likely it is for us to misclassify a test case. The threshold between the two means is about 1200 away from each of them, which is about 18 standard deviations of either distribution. For a normal distribution the probability that a specific outcome lands more than \(18\sigma\) away to a specific side is about \(10^{-73}\), and from the central limit theorem we know that our distribution will already be pretty close to normal. Thus, it’s essentially impossible to get a test case that would get misclassified.
The final solution we derived above is really simple:
