Mathematics Colloquia and Seminars
Mixing time for the top swap shuffleMathematical Physics & Probability
|Speaker:||Ben Morris, UC Davis|
|Start time:||Wed, Dec 6 2017, 4:10PM|
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.