{
  "id": "1308.5459",
  "version": "v2",
  "published": "2013-08-25T22:40:52.000Z",
  "updated": "2014-04-27T15:43:10.000Z",
  "title": "Unseparated pairs and fixed points in random permutations",
  "authors": [
    "Persi Diaconis",
    "Steven N. Evans",
    "Ron Graham"
  ],
  "comment": "revised to incorporate corrections suggested by referee",
  "categories": [
    "math.PR",
    "math.CO"
  ],
  "abstract": "In a uniform random permutation \\Pi of [n] := {1,2,...,n}, the set of elements k in [n-1] such that \\Pi(k+1) = \\Pi(k) + 1 has the same distribution as the set of fixed points of \\Pi that lie in [n-1]. We give three different proofs of this fact using, respectively, an enumeration relying on the inclusion-exclusion principle, the introduction of two different Markov chains to generate uniform random permutations, and the construction of a combinatorial bijection. We also obtain the distribution of the analogous set for circular permutations that consists of those k in [n] such that \\Pi(k+1 mod n) = \\Pi(k) + 1 mod n. This latter random set is just the set of fixed points of the commutator [\\rho, \\Pi], where \\rho is the n-cycle (1,2,...,n). We show for a general permutation \\eta that, under weak conditions on the number of fixed points and 2-cycles of \\eta, the total variation distance between the distribution of the number of fixed points of [\\eta,\\Pi] and a Poisson distribution with expected value 1 is small when n is large.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2014-04-27T15:43:10.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "60C05",
      "60B15",
      "60F05"
    ],
    "keywords": [
      "fixed points",
      "unseparated pairs",
      "distribution",
      "generate uniform random permutations",
      "total variation distance"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2013arXiv1308.5459D"
    }
  }
}