{
  "id": "math/0403259",
  "version": "v2",
  "published": "2004-03-16T12:59:07.000Z",
  "updated": "2004-10-14T07:32:44.000Z",
  "title": "A phase transition in the random transposition random walk",
  "authors": [
    "Nathanael Berestycki",
    "Rick Durrett"
  ],
  "comment": "Revisions include considerable changes in the presentation of section 6 (proof of the CLT in the supercritical regime), and several typos corrected. Also, the figures are now available as a separate .ps file",
  "categories": [
    "math.PR",
    "math.CO"
  ],
  "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} \\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.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2004-10-14T07:32:44.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "60G50",
      "05C80",
      "60F05"
    ],
    "keywords": [
      "random transposition random walk",
      "phase transition",
      "random graph model",
      "random transposition walk",
      "simulation study"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2004math......3259B"
    }
  }
}