Friday April 27, 2018 3:15pm Yost 306

Speaker: Megan M. Bernstein, Georgia Institute of Technology Department of Mathematics

Abstract: Cutoff is a remarkable property of many Markov chains in which they after number of steps abruptly transition in a smaller order window from an unmixed to a mixed distribution. Most random walks on the symmetric group, also known as card shuffles, are believed to mix with cutoff, but we are far from being able to prove this. Spectral techniques are one of the few known that are strong enough to give cutoff, but diagonalization is difficult for random walks on groups where the generators of the walk are not conjugation invariant. Using a diagonalization by Dieker and Saliola , I will show an upper bound that, together with a lower bound from Subag, gives that cutoff occurs for the random-to-random card shuffle on n cards at 3/4n log n – 1/4n log log n ± cn steps (answering a 2001 conjecture of Diaconis). Includes joint work with Evita Nestorid.