Return to Colloquia & Seminar listing
Improved mixing time bounds for the L-reversal chain and Thorp shuffle.
Student-Run Research| Speaker: | Ben Morris, UC Davis |
| Location: | 2112 MSB |
| Start time: | Wed, Jan 24 2007, 12:10PM |
Description
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.