Limiting Distribution of Fixed Points of a Random Function
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$.
- What is the exact distribution of $F_n$ for finite $n$?
- 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?
- 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.