How Many Shuffles to Randomize a Deck of Cards?

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

• Richard Brierley (TCM)
• Friday 16 January 2009, 16:00-16:30
• TCM Seminar Room, Cavendish Laboratory.

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.

This talk is included in these lists:

• All Cavendish Laboratory Seminars
• All Talks (aka the CURE list)
• Centre for Health Leadership and Enterprise
• Featured lists
• ME Seminar
• Neurons, Fake News, DNA and your iPhone: The Mathematics of Information
• Quantum Matter Journal Club
• School of Physical Sciences
• TCM Journal Club
• TCM Seminar Room, Cavendish Laboratory
• TQS Journal Clubs
• Thin Film Magnetic Talks

Note that ex-directory lists are not shown.