Rutgers Discrete Mathematics Seminar

Title: Cutoff for random to random

Speaker: Evita Nestoridi, Princeton University

Date: Monday, November 13, 2017 2:00 pm

Location: Hill Center, Room 705, Rutgers University, Busch Campus, Piscataway, NJ


Random to random is a card shuffling model that was created to study strong stationary times. Although the mixing time of random to random has been known to be of order nlogn since 2002, cutoff had been an open question for many years, and a strong stationary time giving the correct order for the mixing time is still not known. In joint work with Megan Bernstein, we use the eigenvalues of the random to random card shuffling to prove a sharp upper bound for the total variation mixing time. Combined with the lower bound due to Subag, we prove that this walk exhibits cutoff at 3/4(nlogn), answering a conjecture of Diaconis.