Skip to main content
Journal cover image

A phase transition in the random transposition random walk

Publication ,  Journal Article
Berestycki, N; Durrett, R
Published in: Probability Theory and Related Fields
January 1, 2006

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.

Duke Scholars

Published In

Probability Theory and Related Fields

DOI

ISSN

0178-8051

Publication Date

January 1, 2006

Volume

136

Issue

2

Start / End Page

203 / 233

Related Subject Headings

  • Statistics & Probability
  • 4905 Statistics
  • 4904 Pure mathematics
  • 0104 Statistics
  • 0102 Applied Mathematics
  • 0101 Pure Mathematics
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Berestycki, N., & Durrett, R. (2006). A phase transition in the random transposition random walk. Probability Theory and Related Fields, 136(2), 203–233. https://doi.org/10.1007/s00440-005-0479-7
Berestycki, N., and R. Durrett. “A phase transition in the random transposition random walk.” Probability Theory and Related Fields 136, no. 2 (January 1, 2006): 203–33. https://doi.org/10.1007/s00440-005-0479-7.
Berestycki N, Durrett R. A phase transition in the random transposition random walk. Probability Theory and Related Fields. 2006 Jan 1;136(2):203–33.
Berestycki, N., and R. Durrett. “A phase transition in the random transposition random walk.” Probability Theory and Related Fields, vol. 136, no. 2, Jan. 2006, pp. 203–33. Scopus, doi:10.1007/s00440-005-0479-7.
Berestycki N, Durrett R. A phase transition in the random transposition random walk. Probability Theory and Related Fields. 2006 Jan 1;136(2):203–233.
Journal cover image

Published In

Probability Theory and Related Fields

DOI

ISSN

0178-8051

Publication Date

January 1, 2006

Volume

136

Issue

2

Start / End Page

203 / 233

Related Subject Headings

  • Statistics & Probability
  • 4905 Statistics
  • 4904 Pure mathematics
  • 0104 Statistics
  • 0102 Applied Mathematics
  • 0101 Pure Mathematics