The expected number of fixed points of a random permutation
Statement
A permutation of is chosen uniformly at random. Let be its number of fixed points ().
- Show that for every .
- Show that for every , and deduce the variance of .
Hint
Write where is the indicator of the event "". Expectation is additive even when the are dependent. For part 2, counts ordered pairs of distinct fixed points.
Show solutionHide solution
Solution
1. For each , is uniformly distributed on , so . By linearity,
2. , the number of ordered pairs , , of fixed points. For ,
There are ordered pairs, so .
Variance. , so .
Check. For a computer enumeration of the permutations gives exactly .
Remark. The fixed points are far from independent (if points are fixed, so is the last one), yet linearity of expectation does not care. For : is or with probability each.
Lesson. Write the quantity as a sum of indicators and use linearity of expectation: no independence needed.