Groups & dynamics: Robert Hough (IAS) - Mixing and cut-off on cyclic groups

Thu, 17/12/201512:00-13:00
Einstein 110
Consider a sequence of random walks on $\mathbb{Z}/p\mathbb{Z}$ with symmetric generating sets $A= A(p)$. I will describe known and new results regarding the mixing time and cut-off. For instance, if the sequence $|A(p)|$ is bounded then the cut-off phenomenon does not occur, and more precisely I give a lower bound on the size of the cut-off window in terms of $|A(p)|$. A natural conjecture from random walk on a graph is that the total variation mixing time is bounded by maximum degree times diameter squared. I prove this conjecture in the context of random walk on the Cayley graph $(\mathbb{Z}/p\mathbb{Z}, A)$. I also study the typical and worst case behavior of random walk with random generating set chosen uniformly from among all sets of a given size. Time permitting I will also describe the mixing analysis of the walk generated by the powers of 2 less than p, which has features similar to random walk on the hypercube.