Wednesday October 20th, 2021 | |
| Time: | 4:30 PM |
| Title: | Spectral techniques in Markov chain mixing |
| Speaker: | Evita Nestoridi, Princeton University |
| Abstract: | |
| How many steps does it take to shuffle a deck of $n$ cards, if at each step we pick two cards uniformly at random and swap them? Diaconis and Shahshahani proved that $\frac{1}{2} n log n$ steps are necessary and sufficient to mix the deck. Using the representation theory of the symmetric group, they proved that this random transpositions card shuffle exhibits a sharp transition from being unshuffled to being very well shuffled. This is called the cutoff phenomenon. In this talk, I will explain how to use the spectral information of a Markov chain to study cutoff. As an application, I will briefly discuss the random-to-random card shuffle (joint with M. Bernstein) and the non-backtracking random walk on Ramanujan graphs (joint with P. Sarnak). | |