A phase transition in the random transposition random walk
Loading...
Date
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Description
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} \sim u(c)n$, where $u$ is an explicit function satisfying $u(c)=c/2$ for $c \le 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.
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
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