## A phase transition in the random transposition random walk

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

## DOI

## ISSN

## Publication Date

## Volume

## Issue

## Start / End Page

## Related Subject Headings

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

### Citation

*Probability Theory and Related Fields*,

*136*(2), 203–233. https://doi.org/10.1007/s00440-005-0479-7

*Probability Theory and Related Fields*136, no. 2 (January 1, 2006): 203–33. https://doi.org/10.1007/s00440-005-0479-7.

*Probability Theory and Related Fields*, vol. 136, no. 2, Jan. 2006, pp. 203–33.

*Scopus*, doi:10.1007/s00440-005-0479-7.

## Published In

## DOI

## ISSN

## Publication Date

## Volume

## Issue

## Start / End Page

## Related Subject Headings

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