Cutoff for the random to random shuffle

ACO Student Seminar
Friday, April 28, 2017 - 13:05
1 hour (actually 50 minutes)
Skiles 005
School of Mathematics, Georgia Tech
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 total variation 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 Young tableaux. Joint work with Evita Nestorid.