A phase transition in the random transposition random walk


Journal Article

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̃ u(c)n, where u is an explicit function satisfying u(c)=c/2 for c ≤ 1 and u(c)1. In addition, we describe the fluctuations of D cn/2 about its mean in each of the three regimes (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 Erdos-Renyi random graph model.

Full Text

Duke Authors

Cited Authors

  • Berestycki, N; Durrett, R

Published Date

  • January 1, 2006

Published In

Volume / Issue

  • 136 / 2

Start / End Page

  • 203 - 233

International Standard Serial Number (ISSN)

  • 0178-8051

Digital Object Identifier (DOI)

  • 10.1007/s00440-005-0479-7

Citation Source

  • Scopus