Expected Number of Fixed Points in a Random Permutation

MediumProbability

Reported in interviews at Five Rings Jane Street

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$.

  1. What is the expected number of fixed points?
  1. 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.

Related free problems