{
  "id": "2201.04181",
  "version": "v1",
  "published": "2022-01-11T20:15:04.000Z",
  "updated": "2022-01-11T20:15:04.000Z",
  "title": "Conditional Probability of Derangements and Fixed Points",
  "authors": [
    "Sam Gutmann",
    "Mark Mixer",
    "Steven Morrow"
  ],
  "comment": "16 pages, 2 figures. To be published in Transactions on Combinatorics",
  "categories": [
    "math.CO",
    "math.PR"
  ],
  "abstract": "The probability that a random permutation in $S_n$ is a derangement is well known to be $\\displaystyle\\sum\\limits_{j=0}^n (-1)^j \\frac{1}{j!}$. In this paper, we consider the conditional probability that the $(k+1)^{st}$ point is fixed, given there are no fixed points in the first $k$ points. We prove that when $n \\neq 3$ and $k \\neq 1$, this probability is a decreasing function of both $k$ and $n$. Furthermore, it is proved that this conditional probability is well approximated by $\\frac{1}{n} - \\frac{k}{n^2(n-1)}$. Similar results are also obtained about the more general conditional probability that the $(k+1)^{st}$ point is fixed, given that there are exactly $d$ fixed points in the first $k$ points.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2022-01-11T20:15:04.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05A05",
      "05A19",
      "60C05"
    ],
    "keywords": [
      "fixed points",
      "derangement",
      "general conditional probability",
      "random permutation"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 16,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}