Improved Mixing Time Bounds for the Thorp Shuffle

Improved Mixing Time Bounds for the Thorp Shuffle

Probability Seminar
Feb 17, 2010, 03:00 PM - 04:00 PM | 330 Evans Hall | Happening As Scheduled
Ben Morris, Department of Mathematics, UC Davis (Speaker)
The Thorp shuffle is defined as follows. Cut the deck into two equal piles. Drop the first card from the left pile or the right pile according to a fair coin flip; then drop from the other pile. Continue this way until both piles are empty. We show that the mixing time for the Thorp shuffle with 2^d cards is O(d^3). This improves on the best known bound of O(d^4).