Sie befinden Sich nicht im Netzwerk der Universität Paderborn. Der Zugriff auf elektronische Ressourcen ist gegebenenfalls nur via VPN oder Shibboleth (DFN-AAI) möglich.
mehr Informationen...
Cutoff for conjugacy-invariant random walks on the permutation group
Ist Teil von
Probability theory and related fields, 2019-04, Vol.173 (3-4), p.1197-1241
Ort / Verlag
Berlin/Heidelberg: Springer Berlin Heidelberg
Erscheinungsjahr
2019
Link zum Volltext
Quelle
EBSCOhost Business Source Ultimate
Beschreibungen/Notizen
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
and is strictly positive for
c
>
1
.