A phase transition in the random transposition random walkReportar como inadecuado

A phase transition in the random transposition random walk - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

1 Department of Mathematics Cornell 2 ENS Paris - Ecole normale supérieure

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 ~ ucn$ where u is an explicit function satisfying $ux < 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 : random transposition random graphs phase transition coagulation-fragmentation

Autor: Nathanael Berestycki - Rick Durrett -

Fuente: https://hal.archives-ouvertes.fr/


Documentos relacionados