Cutoff for conjugacy-invariant random walks on the permutation group
Repository URI
Repository DOI
Type
Article
Change log
Authors
Berestycki, Nathanael
Sengul, Bati
Abstract
We prove a conjecture raised by the work of Diaconis and Shahshahani (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 Kantorovitch distance by using a
variant of a coupling due to Oded Schramm. 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
Description
Keywords
Random walks, Symmetric group, Mixing times, Random transpositions, Conjugacy classes, Coalescence and fragmentation, Coarse Ricci curvature
Journal Title
PROBABILITY THEORY AND RELATED FIELDS
Conference Name
Journal ISSN
0178-8051
1432-2064
1432-2064
Volume Title
173
Publisher
Springer Science and Business Media LLC
Publisher DOI
Sponsorship
Engineering and Physical Sciences Research Council (EP/G055068/1)
Engineering and Physical Sciences Research Council (EP/L018896/1)
Engineering and Physical Sciences Research Council (EP/I03372X/1)
Engineering and Physical Sciences Research Council (EP/L018896/1)
Engineering and Physical Sciences Research Council (EP/I03372X/1)