DSA Notes

Math

Expected Value

The average outcome, and why it splits into simple pieces.

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.
Watch it run

Try your own input

Practise on LeetCode