Cutoff with window for the random to random shuffle - Megan Bernstein

views comments

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 occurs at 3/4n log n - 1/4n log log n ± cn steps (answering a 2001 conjecture of Diaconis). Includes joint work with Evita Nestoridi.

https://mediaspace.gatech.edu/media/bernstein.mpg/1_fa9smkw9

Tags

Cutoff with window for the random to random shuffle - Megan Bernstein

Related Media