Cutoff for product replacement on finite groups

• 成果类型: Article
• 署名作者: Peres, Yuval; Tanaka, Ryokichi; Zhai, Alex
• 署名单位: Tohoku University; University System of Ohio; Kent State University; Kent State University Salem; Kent State University Kent; Stanford University
• 刊物名称: PROBABILITY THEORY AND RELATED FIELDS
• ISSN/ISSBN: 0178-8051
• DOI: 10.1007/s00440-020-00962-1
• 发表日期: 2020
• 页码: 823-853
• 关键词: generating sets; walks; algorithm

摘要

We analyze a Markov chain, known as the product replacement chain, on the set of generating n-tuples of a fixed finite group G. We show that as n. 8, the totalvariation mixing time of the chain has a cutoff at time 3 2 n log n with window of order n. This generalizes a result of Ben-Hamou and Peres (who established the result for G = Z/2) and confirms a conjecture of Diaconis and Saloff-Coste that for an arbitrary but fixed finite group, the mixing time of the product replacement chain is O(n log n).