Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Durrett introduced the following Markov chain, called the "top swap shuffle",
to model the evolution of a genome. Suppose that $n$ cards are separated into $k$ piles. At each step we choose a random pair of positions, where a position is a space above a card or at the bottom of a pile. If the positions are in the same pile we do nothing; otherwise, we cut both piles at the chosen positions and then exchange the top parts of the two piles. We show that the mixing time is
$O(n \log^4 n)$ if $n \geq k$. This bound is within a factor $\log^3 n$ of optimal and improves on the bound that follows from the spectral gap, which was determined (up to constant factors) by Bhatnagar, Caputo, Tetali and Vigoda.

Joint work with Chuan Qin.