Cutoff for conjugacy-invariant random walks on the permutation group
成果类型：
Article
署名作者：
Berestycki, Nathanael; Sengul, Bati
署名单位：
University of Cambridge
刊物名称：
PROBABILITY THEORY AND RELATED FIELDS
ISSN/ISSBN：
0178-8051
DOI：
10.1007/s00440-018-0844-y
发表日期：
2019
页码：
1197-1241
关键词：
摘要：
We prove a conjecture raised by the work of Diaconis and Shahshahani (Z Wahrscheinlichkeitstheorie Verwandte Geb 57(2):159-179, 1981) about the mixing time of random walks on the permutation group induced by a given conjugacy class. To do this we exploit a connection with coalescence and fragmentation processes and control the Kantorovich distance by using a variant of a coupling due to Oded Schramm as well as contractivity of the distance. Recasting our proof in the language of Ricci curvature, our proof establishes the occurrence of a phase transition, which takes the following form in the case of random transpositions: at time cn/2, the curvature is asymptotically zero for c1 and is strictly positive for c>1.
来源URL：