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$.
Hints
- The events are dependent, but you do not need independence to sum expectations. Think about indicator random variables.
- For each position $i$, what fraction of the $n$ possible values are strictly greater than $i$?
- Compute $E[X_i] = (n - i)/n$ for each $i$ and sum: $\sum_{i=1}^n (n-i)/n = (n-1)/2$.
Worked Solution
How to Think About It: You have a random permutation and you want to count how many positions end up with a value bigger than their index. The events "position $i$ is a winner" are dependent -- if $\sigma(1) = 5$, that changes what is available for position 5. But the beauty of linearity of expectation is that you do not need independence. Just compute $P(\sigma(i) > i)$ for each $i$ separately and add them up.
Quick gut check: by symmetry, for each position $i$, the value $\sigma(i)$ is equally likely to be any of the $n$ values. So $P(\sigma(i) > i) = (n - i)/n$. Sum that over $i = 1, \dots, n$ and you get something close to $n/2$.
Quick Estimate: For $n = 25$, the expected count is $\sum_{i=1}^{25} (25 - i)/25 = (24 + 23 + \cdots + 0)/25 = 300/25 = 12$. Done.
Approach: Indicator random variables plus linearity of expectation.
Formal Solution:
Define $X_i = \mathbf{1}\{\sigma(i) > i\}$ for $i = 1, \dots, n$. The total count of winners is $T = \sum_{i=1}^n X_i$.
By linearity of expectation:
$$E[T] = \sum_{i=1}^n E[X_i] = \sum_{i=1}^n P(\sigma(i) > i)$$
Since $\sigma$ is a uniform random permutation, $\sigma(i)$ is equally likely to be any element of $\{1, \dots, n\}$. The number of values strictly greater than $i$ is $n - i$, so:
$$P(\sigma(i) > i) = \frac{n - i}{n}$$
Summing:
$$E[T] = \sum_{i=1}^n \frac{n - i}{n} = \frac{1}{n} \sum_{j=0}^{n-1} j = \frac{1}{n} \cdot \frac{(n-1)n}{2} = \frac{n-1}{2}$$
Answer: The expected number of winners is $(n-1)/2$. For $n = 25$, this equals $\boxed{12}$.
Intuition
This problem is a showcase for linearity of expectation -- one of the most powerful tools in a quant's toolkit. The key insight is that you never need to untangle the dependence structure between the indicators. Each $X_i$ lives in its own little world for the purpose of computing $E[X_i]$, and the total expectation is just the sum. This pattern recurs constantly: expected number of fixed points in a permutation (answer: 1), expected number of records, expected number of inversions -- all solved the same way.
Note the elegant symmetry: by the same logic, the expected number of positions where $\sigma(i) < i$ is also $(n-1)/2$, and the expected number of fixed points ($\sigma(i) = i$) is 1. These three quantities sum to $n$, as they must.