BIRS Workshop Lecture Videos
Cutoff for the Random to Random Shuffle Bernstein, Megan
(joint work with Evita Nestoridi) The random to random shuffle on a deck of cards is given by at each step choosing a random card from the deck, removing it, and replacing it in a random location. We show an upper bound for the mixing time of the walk of $3/4n\log(n) +cn$ steps. Together with matching lower bound of Subag (2013), this shows the walk mixes with cutoff at $3/4n\log(n)$ steps, answering a conjecture of Diaconis. We use the diagonalization of the walk by Dieker and Saliola (2015), which relates the eigenvalues to skew partitions and desarrangement tableaux.
Item Citations and Data
Attribution-NonCommercial-NoDerivatives 4.0 International