University of Cambridge > Talks.cam > TCM Journal Club > How Many Shuffles to Randomize a Deck of Cards?

How Many Shuffles to Randomize a Deck of Cards?

Add to your list(s) Download to your calendar using vCal

If you have a question about this talk, please contact Daniel Cole.

Proc. Roy. Soc. 456, 2561 (2000) L. N. Trefethen and 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 M X , 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 talk is part of the TCM Journal Club series.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.

 

© 2006-2021 Talks.cam, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity