[My Computational Complexity Web Log] Persi Diaconis
Persi Diaconis once again shatters our belief in generating randomness; this time showing, with Susan Holmes and Richard Montgomery, that flipping coins does not usually produce uniformly random bits.
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.
Posted by Lance Fortnow to My Computational Complexity Web Log at 3/2/2004 06:24:33 PM