Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Durrett introduced the following "L-reversal model" for evolution of a genome. There are n cards arrayed in a circle. Each step, an interval of cards of length at most L is chosen uniformly at random and its order is reversed.

E. Thorp introduced the following model of a card shuffle in 1973. 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 until both piles are empty.

We prove a theorem about card shuffling that yields mixing time bounds for both the L-reversal model and Thorp shuffle that are within a few logarithmic factors of optimal. Previously, the best bounds had been n^{2/3} times optimal for the L-reversal model and more than (log n)^{25} times optimal for the Thorp shuffle. Previous proofs for the Thorp shuffle had been valid only when n is a power of two.