Conditional Probability of Derangements and Fixed Points

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...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2022-01
Main Authors: Gutmann, Sam, Mixer, Mark, Morrow, Steven
Format: Article
Language:English
Subjects:
Conditional probability
Permutations
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:2331-8422