Expected Number of Fixed Points in a Random Permutation
Problem statement
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?
Show hint
Can you write the count as a sum of simple yes/no variables, one per element, and use a property of expectation that ignores dependence?
Relevant roles: Data Scientist, Applied Scientist and Research Scientist.