Séance Séminaire

Séminaire Gaston Darboux

Cutoff for product replacement on finite groups

We analyze a Markov chain, known as the product replacement chain, on the set of generating n-tuples of a fixed finite group G. This chain has been studied as an algorithm which produces a nearly uniform random element in a finite group G. It is also a part of large class of Markov chains such as a random walk on SL(n, Z/q) driven by uniform elementary row operations, and particle systems on complete graphs. Based on joint work with Yuval Peres and Alex Zhai, we show that for any finite group G (which is fixed), the total-variation mixing time is O(n log n); moreover it exhibits a cutoff at time (3/2)n log n as n tends to infinity. The previous known bound was O(n^2 log n) due to Diaconis and Saloff-Coste. We also discuss related questions to this chain.