Math @ Duke
|
Publications [#243548] of Richard T. Durrett
Papers Published
- Berestycki, N; Durrett, R, A phase transition in the random transposition random walk,
Probability Theory and Related Fields, vol. 136 no. 2
(January, 2006),
pp. 203-233, Springer Nature, ISSN 0178-8051 [MR2240787 (2007i:60009)], [doi]
(last updated on 2024/04/24)
Abstract: 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.
|
|
dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
| |
Mathematics Department
Duke University, Box 90320
Durham, NC 27708-0320
|
|