How many shuffles to randomize a deck of cards?

L. N. Trefethen, L. M. Trefethen


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.

Royal Society Login

Log in through your institution