Cutoff for conjugacy-invariant random walks on the permutation group

Abstract

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 c≤1$$c\le 1$$ and is strictly positive for c>1$$c>1$$.