# Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

### Mixing time for the top swap shuffle

Mathematical Physics & Probability

 Speaker: Ben Morris, UC Davis Related Webpage: https://www.math.ucdavis.edu/people/general-profile?fac_id=morris Location: 1147 MSB 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.