Expected Number of Fixed Points in a Random Permutation
A permutation $\pi$ of $\{1, 2, \ldots, n\}$ is chosen uniformly at random. A fixed point is an element $i$ such that $\pi(i) = i$.
- What is the expected number of fixed points?
- What is the variance of the number of fixed points?
Hints
- Define indicator random variables $X_i = \mathbf{1}[\pi(i) = i]$ and use linearity of expectation. You do not need independence.
- For the variance, compute $E[X_i X_j]$ for $i \neq j$ -- this is the probability that both $i$ and $j$ are fixed points simultaneously.
- $P(\pi(i) = i \text{ and } \pi(j) = j) = \frac{1}{n(n-1)}$. There are $n(n-1)$ such pairs. Watch everything cancel.
Worked Solution
How to Think About It: The trick is to avoid thinking about the global structure of the permutation. Instead, decompose the count into indicators -- one for each position. Each indicator asks a simple question: "does element $i$ stay in place?" Linearity of expectation handles the rest, even though the indicators are not independent. This is probably the single most important technique in combinatorial probability.
Quick Estimate: Each element has a $1/n$ chance of being a fixed point, and there are $n$ elements. By linearity, the expected count is $n \cdot 1/n = 1$. Done. The beautiful part: this does not depend on $n$ at all.
Formal Solution:
Part 1: Expected value.
Define indicator random variables $X_i = \mathbf{1}[\pi(i) = i]$ for $i = 1, \ldots, n$. The total number of fixed points is $X = \sum_{i=1}^n X_i$.
Each element is equally likely to map to any of the $n$ positions, so: $$P(\pi(i) = i) = \frac{1}{n}$$
By linearity of expectation (no independence needed): $$E[X] = \sum_{i=1}^n E[X_i] = \sum_{i=1}^n \frac{1}{n} = 1$$
Part 2: Variance.
We need $\text{Var}(X) = E[X^2] - (E[X])^2$. Expand: $$E[X^2] = E\left[\left(\sum_{i=1}^n X_i\right)^2\right] = \sum_{i=1}^n E[X_i^2] + \sum_{i \neq j} E[X_i X_j]$$
Since $X_i$ is an indicator, $X_i^2 = X_i$, so $E[X_i^2] = 1/n$ and: $$\sum_{i=1}^n E[X_i^2] = n \cdot \frac{1}{n} = 1$$
For the cross terms ($i \neq j$): $X_i X_j = 1$ iff both $\pi(i) = i$ AND $\pi(j) = j$. The probability that $i$ maps to itself is $1/n$, and given that, the probability $j$ maps to itself (among the remaining $n-1$ elements) is $1/(n-1)$: $$E[X_i X_j] = P(\pi(i) = i \text{ and } \pi(j) = j) = \frac{1}{n} \cdot \frac{1}{n-1}$$
There are $n(n-1)$ ordered pairs $(i, j)$ with $i \neq j$: $$\sum_{i \neq j} E[X_i X_j] = n(n-1) \cdot \frac{1}{n(n-1)} = 1$$
Therefore: $$E[X^2] = 1 + 1 = 2$$ $$\text{Var}(X) = E[X^2] - (E[X])^2 = 2 - 1 = 1$$
Answer: The expected number of fixed points is $E[X] = 1$ and the variance is $\text{Var}(X) = 1$, both independent of $n$.
Remark: As $n \to \infty$, the distribution of fixed points converges to $\text{Poisson}(1)$. This is consistent with both the mean and variance equaling 1. The convergence follows because the indicators $X_i$ become "approximately independent" for large $n$, and a sum of many rare, nearly independent indicators is approximately Poisson.
Intuition
This problem is the poster child for indicator random variables and linearity of expectation. The beauty is that linearity works regardless of dependence -- you never need to think about the complicated joint structure of the permutation. Each position contributes $1/n$ in expectation, and $n$ positions add up to 1. Period.
The variance calculation is more subtle because it requires pairwise joint probabilities, but the answer is equally clean: variance is also 1, independent of $n$. This is a strong hint that the distribution is Poisson(1) in the limit, which it is. In quant work, this technique of decomposing a complex count into indicators is used constantly -- counting exceedances, default events, signal hits, or pattern matches in sequences. Whenever you need the expected count of "how many things satisfy property X," reach for indicators first.