Limiting Distribution of Fixed Points of a Random Function

MediumProbability

Problem statement

Pick a function $f_n: [n] \to [n]$ uniformly at random from the set of all $n^n$ functions, where $[n] = \{1, 2, \dots, n\}$. A fixed point is an index $i$ such that $f_n(i) = i$. Let $F_n$ denote the number of fixed points of $f_n$.

  1. What is the exact distribution of $F_n$ for finite $n$?
  2. What is the limiting distribution of $F_n$ as $n \to \infty$? That is, for any non-negative integer $k$, what does $P(F_n = k)$ converge to?
  3. Compute $\displaystyle \lim_{n \to \infty} P(F_n = 3)$ to the nearest thousandth.
Show hint

How could you write the total number of fixed points as a sum of simpler pieces, one per index?

Relevant roles: Research Scientist, Data Scientist, Applied Scientist and ML Engineer.

Related free problems