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.
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
Liste complète des métadonnées

Littérature citée [25 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00001309
Contributeur : Coordination Episciences Iam <>
Soumis le : mercredi 12 août 2015 - 09:08:13
Dernière modification le : jeudi 11 mai 2017 - 01:02:54
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

Collections

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〉

Partager

Métriques

Consultations de la notice

68

Téléchargements de fichiers

46