The 20th Northwest Probability Seminar: Cutoff for Product Replacement on Finite Groups

  • Alex Zhai | Stanford University

Let G be a finite group, and consider the following \emph{product replacement walk} on the set of generating n-tuples of elements of G: randomly pick two of the n elements, say g and h, and replace g with either gh or gh−1, with equal probability. This walk has been studied in the context of computational group theory for its mixing properties. It can also be seen as part of a more general class of Markov chains that includes random walks on the group of invertible matrices SLn(Fq) and the East model in interacting particle systems. In this talk, based on joint work with Yuval Peres and Ryokichi Tanaka, we show that as n→∞ (with G fixed), the total-variation mixing time of the product replacement walk has a cutoff at time 3/2nlogn with window of order nn. This generalizes a recent result of Ben-Hamou and Peres, who established the result for G=Z/2. For general groups, the previous best bound due to Diaconis and Saloff-Coste was O(n²logn), who also conjectured the bound O(nlogn).

View presentation slides here: https://www.microsoft.com/en-us/research/wp-content/uploads/2018/11/Cutoff-for-Product-Replacement-on-Finite-Groups-SLIDES.pdf

Watch Next