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

Опубликовано 21 ноября 2018, 20:18

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).

See more at microsoft.com/en-us/research/v...