{
  "id": "math/0412449",
  "version": "v2",
  "published": "2004-12-22T12:05:06.000Z",
  "updated": "2006-10-11T14:33:07.000Z",
  "title": "Relaxation time of $L$-reversal chains and other chromosome shuffles",
  "authors": [
    "N. Cancrini",
    "P. Caputo",
    "F. Martinelli"
  ],
  "comment": "Published at http://dx.doi.org/10.1214/105051606000000295 in the Annals of Applied Probability (http://www.imstat.org/aap/) by the Institute of Mathematical Statistics (http://www.imstat.org)",
  "journal": "Annals of Applied Probability 2006, Vol. 16, No. 3, 1506-1527",
  "doi": "10.1214/105051606000000295",
  "categories": [
    "math.PR"
  ],
  "abstract": "We prove tight bounds on the relaxation time of the so-called $L$-reversal chain, which was introduced by R. Durrett as a stochastic model for the evolution of chromosome chains. The process is described as follows. We have $n$ distinct letters on the vertices of the ${n}$-cycle (${{\\mathbb{Z}}}$ mod $n$); at each step, a connected subset of the graph is chosen uniformly at random among all those of length at most $L$, and the current permutation is shuffled by reversing the order of the letters over that subset. We show that the relaxation time $\\tau (n,L)$, defined as the inverse of the spectral gap of the associated Markov generator, satisfies $\\tau (n,L)=O(n\\vee \\frac{n^3}{L^3})$. Our results can be interpreted as strong evidence for a conjecture of R. Durrett predicting a similar behavior for the mixing time of the chain.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2006-10-11T14:33:07.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "60J27",
      "92D10"
    ],
    "keywords": [
      "relaxation time",
      "reversal chain",
      "chromosome shuffles",
      "strong evidence",
      "similar behavior"
    ],
    "tags": [
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2004math.....12449C"
    }
  }
}