Mathematics Colloquia and Seminars

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.