A phase transition in the random transposition random walk
| dc.creator | Berestycki, Nathanael | |
| dc.creator | Durrett, Rick | |
| dc.date | 2004-03-16 | |
| dc.date | 2004-10-14 | |
| dc.date.accessioned | 2026-07-07T05:06:27Z | |
| dc.date.available | 2026-07-07T05:06:27Z | |
| dc.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. | |
| dc.description | 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 | |
| dc.identifier | https://arxiv.org/abs/math/0403259 | |
| dc.identifier | http://arxiv.org/abs/math/0403259 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/70474 | |
| dc.subject | Probability | |
| dc.subject | Combinatorics | |
| dc.subject | 60G50, 05C80, 60F05 | |
| dc.title | A phase transition in the random transposition random walk | |
| dc.type | text |