# A phase transition in the random transposition random walk

Abstract : Our work is motivated by Bourque-Pevzner's simulation study of the effectiveness of the parsimony method in studying genome rearrangement, and leads to a surprising result about the random transposition walk in continuous time on the group of permutations on $n$ elements starting from the identity. Let $D_t$ be the minimum number of transpositions needed to go back to the identity element from the location at time $t$. $D_t$ undergoes a phase transition: for $0 < c ≤ 1$, the distance $D_cn/2 ~ cn/2$, i.e., the distance increases linearly with time; for $c > 1$, $D_cn/2 ~ u(c)n$ where u is an explicit function satisfying $u(x) < x/2$. Moreover we describe the fluctuations of $D_{cn/2}$ about its mean at each of the three stages (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-Rényi random graph model.
Keywords :
Type de document :
Communication dans un congrès
Cyril Banderier and Christian Krattenthaler. Discrete Random Walks, DRW'03, 2003, Paris, France. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AC, Discrete Random Walks (DRW'03), pp.17-26, 2003, DMTCS Proceedings
Domaine :

Littérature citée [25 références]

https://hal.inria.fr/hal-00001309
Contributeur : Coordination Episciences Iam <>
Soumis le : mercredi 12 août 2015 - 09:08:13
Dernière modification le : vendredi 16 mars 2018 - 14:44:02
Document(s) archivé(s) le : vendredi 13 novembre 2015 - 11:38:07

### Fichier

dmAC0102.pdf
Fichiers éditeurs autorisés sur une archive ouverte

### Identifiants

• HAL Id : hal-00001309, version 3

### Citation

Nathanael Berestycki, Rick Durrett. A phase transition in the random transposition random walk. Cyril Banderier and Christian Krattenthaler. Discrete Random Walks, DRW'03, 2003, Paris, France. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AC, Discrete Random Walks (DRW'03), pp.17-26, 2003, DMTCS Proceedings. 〈hal-00001309v3〉

### Métriques

Consultations de la notice

## 100

Téléchargements de fichiers