Diaconis has an impressive resume of magic, mathematics and psychic debunking. Around 1990 he visited Chicago and taught a course on Markov chain analysis spending the first half of the course on the following problem: Given n cards, pick two at random and swap them. Repeat. How many swaps do you need to get a nearly randomly shuffled deck? Answer: About n log n. The upper bound used representation theory and took several weeks to prove.

During that year, a Chicago Tribune editorial mentioned another Diaconis result showing that one needs seven standard shuffles to get a deck of cards close to random. I found the beginning of the editorial online:

*
And you always thought mathematicians were serious people. Especially
those at Ivy League universities like Harvard and Columbia. Well ...
*

*
Dr. Persi Diaconis and Dr. Dave Bayer have just come out with a study
that may give you pause. They have found, after no end of riffling and
counting, that it takes exactly seven ordinary, careless shuffles to
give a totally random mix to ...*

Getting back to coin flipping, you can always use the von Neumann coin-flipping trick to correct for the unknown bias.

## No comments:

## Post a Comment