Mathematics – Probability
Scientific paper
2004-03-16
Mathematics
Probability
Revisions include considerable changes in the presentation of section 6 (proof of the CLT in the supercritical regime), and se
Scientific paper
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} \sim u(c)n$, where $u$ is an explicit function satisfying $u(c)=c/2$ for $c \le 1$ and $u(c)1$. In other words, the distance to the identity is roughly linear during the subcritical phase, and after critical time $n/2$ it becomes sublinear. In addition, we describe the fluctuations of $D_{cn/2}$ about its mean in each of the threeregimes (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 \Erd\H{o}s-Renyi random graph model.
Berestycki Nathanael
Durrett Rick
No associations
LandOfFree
A phase transition in the random transposition random walk does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with A phase transition in the random transposition random walk, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A phase transition in the random transposition random walk will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-574526