# 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.