Cutoff for conjugacy-invariant random walks on the permutation group

被引：7

作者：

Berestycki, Nathanael ^{[1
]}

Sengul, Bati ^{[1
]}

机构：

[1] Univ Cambridge, Stat Lab, Cambridge, England

来源：

PROBABILITY THEORY AND RELATED FIELDS | 2019年 / 173卷 / 3-4期

基金：

英国工程与自然科学研究理事会;

关键词：

Random walks; Symmetric group; Mixing times; Random transpositions; Conjugacy classes; Coalescence and fragmentation; Coarse Ricci curvature;

D O I：

10.1007/s00440-018-0844-y

中图分类号：

O21 [概率论与数理统计]; C8 [统计学];

学科分类号：

020208 ; 070103 ; 0714 ;

摘要：

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.

引用

页码：1197 / 1241

页数：45