Conditional probability of derangements and fixed points

Document Type : Research Paper

Authors

1 Department of Mathematics, Northeastern University, 360 Huntington Ave, Boston, MA, USA.

2 School of Computing and Data Science, Wentworth Institute of Technology, 550 Huntington Ave, Boston, MA, USA.

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.

Keywords

Main Subjects

References

[1] T. Antonelli, A surprising link between integer partitions and Euler’s number e, Amer. Math. Monthly, 126 (2019)
418–429.
[2] C. D. Evans, J. Hughes and J. Houston, Significance-testing the validity of idiographic methods: A little derangement
goes a long way, British Journal of Mathematical and Statistical Psychology, 55 (2002) 385–390.
[3] W. Feller, An Introduction to Probability Theory and Its Applications, 1, Third edition John Wiley & Sons, Inc.,
New York-London-Sydney, 1968.
[4] P. C. Fishburn, P. G. Doyle and L. A. Shepp, The match set of a random permutation has the FKG property, Ann.
Probab., 16 (1988) 1194–1214.
[5] S. Fisk, The secretary’s packet problem, Math. Mag., 61 (1988) 103–105.
[6] D. Hanson, K. Seyffarth and J. H. Weston, Matchings, derangements, rencontres, Math. Mag., 56 (1983) 224–229.
[7] S. G. Penrice, Derangements, permanents, and christmas presents, Amer. Math. Monthly, 98 (1991) 617–620.
[8] D. Rawlings, The poisson variation of montmort’s matching problem, Math. Mag., 73 (2000) 232–234.
[9] L. Tak´acs, The problem of coincidences, Arch. Hist. Exact Sci., 21 (1979/80) 229–244. 

Files

History

  • Receive Date: 01 December 2021
  • Revise Date: 11 January 2022
  • Accept Date: 29 January 2022
  • Published Online: 01 March 2023

Share

How to cite

Statistics