A phase transition in the random transposition random walk

• 成果类型: Article
• 署名作者: Berestycki, Nathanael; Durrett, Rick
• 署名单位: Universite PSL; Ecole Normale Superieure (ENS); Cornell University
• 刊物名称: PROBABILITY THEORY AND RELATED FIELDS
• ISSN/ISSBN: 0178-8051
• DOI: 10.1007/s00440-005-0479-7
• 发表日期: 2006
• 页码: 203-233
• 关键词: genome rearrangements; EVOLUTION

摘要

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 similar to(c)n, where u is an explicit function satisfying u(c)=c/2 for c <= 1 and u(c)< c/2 for 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.