Abstract
In the Gilbert-Shannon-Reeds shuffle, a deck of $N$ cards is cut into two approximately equal parts which are then riffled uniformly at random. Bayer and Diaconis famously showed that this Markov chain undergoes cutoff in total variation after $\frac{3\log(N)}{2 \log(2)}$ shuffles. We establish cutoff for the more general asymmetric riffle shuffles in which one cuts the deck into differently sized parts before riffling. The value of the cutoff point confirms a conjecture of Lalley from 2000. Some appealing consequences are that asymmetry always slows mixing and that total variation mixing is strictly faster than separation and $L^{\infty}$ mixing.
Introduction
The "seven shuffles" rule for a standard 52-card deck is a cornerstone of modern probability, derived from the Gilbert-Shannon-Reeds (GSR) model. In this model, a deck is cut into two roughly equal piles and riffled together. This process exhibits a "cutoff" phenomenon: the deck remains poorly mixed for several shuffles before suddenly transitioning to near-perfect randomness.
However, the standard GSR model assumes a symmetric cut ($p=1/2$). In practice, shufflers often exhibit bias, cutting the deck into unequal piles—an asymmetric $p$-shuffle. While it has long been conjectured that these biased shuffles also exhibit cutoff, proving this required overcoming significant technical hurdles, as the traditional combinatorial tools used for symmetric shuffles do not easily generalize to the asymmetric case.
Methods
The proof, developed by Mark Sellke, shifts from combinatorial counting to a robust probabilistic and information-theoretic framework:
- Inverse Permutations and Shuffle Graphs: By analyzing the inverse of the shuffled deck, the process is modeled as a "shuffle graph" where edges represent cards maintaining their relative order.
- Chi-Squared Bounds: To establish the upper bound for mixing, the author employs a chi-squared bound on total variation distance, estimating truncated exponential moments of shared edges between independent shuffles.
- Stable Block Decomposition: The deck is partitioned into "stable blocks" based on "digit profiles," which track the history of a card's placement in the top or bottom pile across multiple shuffles.
- Entropy and KL Divergence: These tools help identify "worst-case" card sequences that are the most resistant to randomization.
Key Insights: The Cost of Asymmetry
A primary finding of this work is that the symmetric $p=1/2$ shuffle is the most efficient method for randomization. Any deviation from this perfect split increases the mixing time constant.
Furthermore, the research reveals that Total Variation mixing occurs strictly faster than $L^\infty$ or "separation" distance in asymmetric shuffles. This is due to "cold spots" in the distribution that delay $L^\infty$ mixing more than the average-case measure of Total Variation.
Quantitative Results and Lalley's Conjecture
The paper rigorously confirms the mixing time threshold $\bar{C}_{\mathbf{p}}$ conjectured by Steven Lalley in 2000. The results demonstrate that cutoff is a universal feature of these shuffles, regardless of the number of piles or the specific bias.
For a standard 52-card deck, a symmetric shuffle ($p=0.5$) requires approximately 8.6 shuffles. A 70/30 split ($p=0.7$) increases this to 11.3, while an extreme 95/5 split ($p=0.95$) requires 77 shuffles to achieve the same level of randomness.
Conclusion
This work provides a definitive proof for the existence and location of cutoff in asymmetric riffle shuffles. While the results are primarily asymptotic, they offer clear insights into the dynamics of biased shuffling. Future research may extend these techniques to more complex models, such as shuffles where cards tend to stick together in clusters.
Summary updated