Expected value and random variables
A random variable assigns a number to each outcome. Its expected value is the long-run average, a central tool in analysing algorithms and games.
Random variables
A random variable \(X\) maps outcomes to numbers, such as the number of heads in 10 flips or the running time of a randomised algorithm. Its distribution lists \(P(X = x)\) for each value.
Expected value
\(E(X) = \sum_x x\,P(X = x)\). For one fair die, \(E(X) = \frac{1 + 2 + \cdots + 6}{6} = 3.5\). The expected value need not be a possible outcome; it is the average over many repetitions.
E(X) = \sum_x x\,P(X=x)Linearity of expectation
\(E(X + Y) = E(X) + E(Y)\), always, even when \(X\) and \(Y\) are dependent. This makes hard problems easy. The expected number of people who get their own hat back when hats are randomly returned is \(n \cdot \frac{1}{n} = 1\), whatever \(n\) is, by adding indicator variables for each person.
E(X+Y) = E(X) + E(Y)Indicator variables
An indicator variable is 1 if an event happens and 0 otherwise; its expected value is the event's probability. Counting problems become sums of indicators. Expected number of fixed points, heads, or collisions all yield to this method.
Variance
\(\text{Var}(X) = E[(X - \mu)^2] = E(X^2) - \mu^2\) measures spread. For independent variables, variances add. A fair die has \(E(X^2) = \frac{91}{6}\), so \(\text{Var}(X) = \frac{91}{6} - 3.5^2 = \frac{35}{12}\).
The geometric distribution
The number of trials until the first success, with success probability \(p\), has expected value \(\frac{1}{p}\). On average you roll a die 6 times to see a six. This underlies analyses like the coupon collector problem.
The coupon collector problem
How many random draws, with replacement, are needed to collect all \(n\) types of coupon? After collecting \(k\) types, the wait for a new one is geometric with \(p = \frac{n - k}{n}\). Summing gives \(n\left(1 + \frac{1}{2} + \cdots + \frac{1}{n}\right) \approx n\ln n\). For 50 types, that is about 225 draws.
Expected running time
Randomised algorithms are analysed by expected running time. Quicksort with random pivots runs in \(O(n\log n)\) expected time, even though an unlucky run can take \(O(n^2)\). Hashing with a good hash function gives constant expected lookup time.
Key takeaways
Expected value is a probability-weighted average. Linearity of expectation always holds and turns counting into sums of indicator variables. Variance measures spread. Geometric waits have mean \(1/p\), coupon collecting takes about \(n\ln n\) draws, and algorithms are often judged by expected running time.
Flashcard
A number assigned to each outcome
Check your understanding
Ten fair coins are flipped. Using linearity of expectation, the expected number of heads is: