easy   Probability

Random Fixed Point

A release-checked easy problem for training Poisson, Combinations and Permutations, Bernoulli/Binomial.

Question

Let $f_n: [n] \rightarrow [n]$ be a uniformly random function selected from the set of all functions from $[n]$ to $[n]$, where $[n] = \{1,2,\dots,n\}$. Let $F_n$ be the number of fixed points the random $f_n$ selected. What is the limiting distribution of $F_n$? In other words, for any non-negative integer $k$, what does $\prob{F_n = k}$ converge to? Report $\displaystyle \lim_{n \rightarrow \infty} \prob{F_n = 3}$ to the nearest thousandth.

Practice focus

This Probability problem is tagged Poisson, Combinations and Permutations, Bernoulli/Binomial. State the random variables and conditioning information explicitly, then check the result against boundary cases before opening hints or a solution.

Explore related collections

Reviewed questions in this area

easyBaby BoyReviewed

Probability · SIG, DE Shaw

easyBad BagelReviewed

Probability · SIG, Jane Street