The idea
The expected value of a random quantity X is the average weighted by probability: E[X] = Σ value · P(value).
Linearity: E[X + Y] = E[X] + E[Y], even when X and Y depend on each other. So split a complicated count into indicator variables (1 if something happens, 0 if not); the expectation is just the sum of their probabilities.
For a maximum, it is easier to compute P(max ≤ k) and subtract: P(max = k) = P(max ≤ k) − P(max ≤ k − 1).
Sample problem
1227. Airplane Seat Assignment Probability ↗ Medium
n passengers board a plane with n seats. The first has lost their ticket and picks a seat at random. Everyone after takes their own seat if it is free, otherwise a random free one. What is the probability that the last passenger gets their own seat?
n = 6 output = 0.5
Why the solution works
The probability of an event is the expected value of its indicator (1 if it happens, 0 if not), so it can be computed as an average over the first random choice, each case weighted by 1/m.
Three kinds of case: the first passenger takes their own seat and everyone else sits correctly (value 1); they take the last passenger’s seat (value 0); or they take passenger j’s seat. Then passengers before j sit normally and j becomes the one choosing at random, which is the same problem with fewer seats.
Averaging gives f[m] = (1 + f[2] + … + f[m−1]) / m. A running sum makes each step O(1), and the values all turn out to be ½.
Complexity: O(n) time (the closed form is ½ for n ≥ 2).
Watch out
- Compute
(k/m)ⁿas a power of the fraction. Computing kⁿ and mⁿ separately overflows. - Linearity needs no independence, but
E[X · Y] = E[X] · E[Y]does. - Define precisely what each indicator counts before summing.