A phase transition in the random transposition random walk

2004/03/16 by Nathanaël Berestycki, Nathanael Berestycki, Rick Durrett +2
Computer Science · Mathematics · #05C80 #60F05 #60G50 #Algorithms and Data Compression #Bayesian Methods and Mixture Models #Combinatorics #Combinatorics (math.CO) #Condensed matter physics #Discrete mathematics #FOS: Mathematics #Geometry #Graph #Identity (music) #Mathematics #Permutation (music) #Phase transition #Physics #Probability (math.PR) #Random graph #Random permutation #Random walk #Statistics #Stochastic processes and statistical mechanics #Sublinear function #Symmetric group #Transposition (logic) #math.CO #math.PR #msc:05C80 #msc:60F05 #msc:60G50

paper · pdf · doi:10.48550/arxiv.math/0403259

Revisions include considerable changes in the presentation of section 6 (proof of the CLT in the supercritical regime), and several typos corrected. Also, the figures are now available as a separate .ps file

openalex publication_date 2004/03/16 · arxiv created 2004/10/14 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05

Abstract

Our work is motivated by Bourque and Pevzner's (2002) simulation study of the effectiveness of the parsimony method in studying genome rearrangement, and leads to a surprising result about the random transposition walk on the group of permutations on n elements. Consider this walk in continuous time starting at the identity and let D_t be the minimum number of transpositions needed to go back to the identity from the location at time t. D_t undergoes a phase transition: the distance D_cn/2 ∼ u(c)n, where u is an explicit function satisfying u(c)=c/2 for c ≤ 1 and u(c)1. In other words, the distance to the identity is roughly linear during the subcritical phase, and after critical time n/2 it becomes sublinear. In addition, we describe the fluctuations of D_cn/2 about its mean in each of the threeregimes (subcritical, critical and supercritical). The techniques used involve viewing the cycles in the random permutation as a coagulation-fragmentation process and relating the behavior to the \Erdős-Renyi random graph model.

Related

• Emergence of giant cycles and slowdown transition in random transpositions and k-cycles
• Limiting behavior of the distance of a random walk
• Phase transition for the vacant set left by random walk on the giant component of a random graph
• The Random Transposition Dynamics on Random Regular Graphs and the Gaussian Free Field
• The phase transition in random graphs - a simple proof