Return to Colloquia & Seminar listing
The Mixing Time of the Thorp Shuffle
Special Events| Speaker: | Benjamin Morris, Indiana University |
| Location: | 693 Kerr |
| Start time: | Wed, Jan 26 2005, 4:10PM |
In 1973, Thorp introduced the following card shuffling procedure. Cut the deck into two equal piles. Drop the first card from the left pile or the right pile according to the outcome of a fair coin flip; then drop from the other pile. Continue this way, flipping an independent coin each time, until both piles are empty. Despite its simple description, the Thorp shuffle has been hard to analyze. It has long been believed that the mixing time is polynomial in log of the number of cards. We prove the first such bound.