Expected Positions Exceeding Values in a Random Permutation
A permutation $\sigma$ of $\{1, 2, \dots, n\}$ is chosen uniformly at random. An index $i$ is called a "winner" if $\sigma(i) > i$ -- that is, the value at position $i$ is strictly larger than $i$ itself.
What is the expected number of winners? Give a general formula in terms of $n$, then evaluate it for $n = 25$.
Open the full interactive solver, hints, and worked solution →