How many shuffles to randomize a deck of cards?
- 8 October 2000
- journal article
- Published by The Royal Society in Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences
- Vol. 456 (2002), 2561-2568
- https://doi.org/10.1098/rspa.2000.0625
Abstract
A celebrated theorem of Aldous, Bayer and Diaconis asserts that it takes ∼3/2 log2 n riffle shuffles to randomize a deck of n cards, asymptotically as n → ∞, and that the randomization occurs abruptly according to a 'cut–off phenomenon'. These results depend upon measuring randomness by a quantity known as the total variation distance. If randomness is measured by uncertainty or entropy in the sense of information theory, the behaviour is different. It takes only ∼log2 n shuffles to reduce the information to a proportion arbitrarily close to zero, and ∼3/2 log2 n to reduce it to an arbitrarily small number of bits. At 3/2> log2 n shuffles, ca.0.0601 bits remain, independently of n.This publication has 16 references indexed in Scilit:
- Markov ChainsPublished by Cambridge University Press (CUP) ,1997
- On markov chains with sluggish transientsCommunications in Statistics. Stochastic Models, 1997
- The cutoff phenomenon in finite Markov chains.Proceedings of the National Academy of Sciences of the United States of America, 1996
- Riffle shuffles, cycles, and descentsCombinatorica, 1995
- Hydrodynamic Stability Without EigenvaluesScience, 1993
- Trailing the Dovetail Shuffle to its LairThe Annals of Applied Probability, 1992
- Fluctuation Theory for the Ehrenfest urnAdvances in Applied Probability, 1991
- Eigenvalue Bounds on Convergence to Stationarity for Nonreversible Markov Chains, with an Application to the Exclusion ProcessThe Annals of Applied Probability, 1991
- Geometric Bounds for Eigenvalues of Markov ChainsThe Annals of Applied Probability, 1991
- Entropy and the Central Limit TheoremThe Annals of Probability, 1986