Limiting Distribution of Fixed Points of a Random Function
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.
Hints
- Think about whether $f_n(i) = i$ and $f_n(j) = j$ are independent events. How does this differ from the case of random permutations?
- If you have $n$ independent events each occurring with probability $1/n$, what classical distribution describes their count -- and what does it converge to?
- The count of fixed points is $\text{Bin}(n, 1/n)$. Apply the Poisson limit theorem with $\lambda = n \cdot (1/n) = 1$.
Worked Solution
How to Think About It: The key observation is that for random functions (as opposed to random permutations), the fixed-point indicators are independent. Each element $i$ maps to a uniformly random target in $[n]$, and since any number of elements can map to the same target, whether $f_n(i) = i$ tells you nothing about whether $f_n(j) = j$. This independence is what makes the problem clean. Once you see that, you have $n$ independent Bernoulli trials each with success probability $1/n$ -- a textbook setup for the Poisson limit theorem.
Quick Estimate: Each of $n$ elements is a fixed point with probability $1/n$, so the expected number of fixed points is $n \cdot (1/n) = 1$, regardless of $n$. If the limit is Poisson(1), then $P(F = 3) = e^{-1}/3! = e^{-1}/6 \approx 0.368/6 \approx 0.061$. We can sanity-check: $P(F = 0) \approx 0.368$, $P(F = 1) \approx 0.368$, $P(F = 2) \approx 0.184$, $P(F = 3) \approx 0.061$ -- these sum to about 0.981, leaving small probability in the tail. Looks right.
Approach: Show $F_n \sim \text{Bin}(n, 1/n)$ exactly, then apply the Poisson limit theorem.
Formal Solution:
Define indicator variables $X_i = \mathbf{1}[f_n(i) = i]$ for $i = 1, 2, \dots, n$. Then $F_n = X_1 + X_2 + \cdots + X_n$.
- Each $X_i$ is Bernoulli with $P(X_i = 1) = 1/n$, since $f_n(i)$ is uniform on $[n]$.
- The $X_i$ are mutually independent. This is because $f_n(i)$ and $f_n(j)$ are chosen independently for $i \neq j$ -- each output is drawn independently from $[n]$. (This is the crucial difference from random permutations, where the outputs must be distinct and the indicators become negatively correlated.)
Therefore $F_n$ is a sum of $n$ independent $\text{Bernoulli}(1/n)$ random variables:
$$F_n \sim \text{Bin}(n, 1/n)$$
Now apply the Poisson limit theorem: if $X_n \sim \text{Bin}(n, p_n)$ with $n p_n \to \lambda$, then $X_n \xrightarrow{d} \text{Poisson}(\lambda)$. Here $n \cdot (1/n) = 1$ for all $n$, so $\lambda = 1$ and:
$$F_n \xrightarrow{d} \text{Poisson}(1)$$
For any non-negative integer $k$:
$$\lim_{n \to \infty} P(F_n = k) = \frac{e^{-1}}{k!}$$
For $k = 3$:
$$\lim_{n \to \infty} P(F_n = 3) = \frac{e^{-1}}{3!} = \frac{e^{-1}}{6} \approx \frac{0.36788}{6} \approx 0.06131$$
Answer: The limiting distribution is $\text{Poisson}(1)$, and $\displaystyle \lim_{n \to \infty} P(F_n = 3) = \frac{e^{-1}}{6} \approx 0.061$.
Intuition
The deep point here is the contrast between random functions and random permutations. For permutations, whether $\pi(i) = i$ and $\pi(j) = j$ are not independent -- if $i$ maps to itself, that "uses up" the value $i$ and changes the odds for everyone else. Functions have no such constraint: each output is drawn independently, so the fixed-point indicators are genuinely independent Bernoulli trials. Both cases lead to a Poisson(1) limit, but through very different mechanisms -- for functions it is the Poisson limit theorem applied to exact Binomial$(n, 1/n)$, while for permutations it requires inclusion-exclusion on dependent indicators.
This Poisson(1) limit for fixed points is one of the most ubiquitous results in combinatorial probability. It shows up whenever you count "rare coincidences" among many independent trials -- birthday collisions, coupon collector duplicates, hash table collisions, and matching problems. The pattern is always the same: $n$ events each with probability roughly $1/n$, expected count roughly 1, and the Poisson approximation is excellent even for moderate $n$. In quant interviews, recognizing this pattern immediately signals fluency with probabilistic thinking.