Linearity of Expectation in quant interviews
E[X + Y] = E[X] + E[Y], independent or not. The most over-powered tool in probability.
TRY A PROBLEM NOW · NO SIGNUP
In the classical secretary problem, as n → ∞, what fraction should you reject outright before accepting the next best-so-far candidate?
WHAT IT IS
Linearity of expectation states that for any random variables X and Y (independent or not), E[X + Y] = E[X] + E[Y]. This extends to any finite sum: E[Σ Xᵢ] = Σ E[Xᵢ]. The power lies in the 'independent or not' clause — it lets you decompose complicated random variables into sums of simple indicator variables, compute each expectation trivially, and add them up, all without ever worrying about correlations. In quant interviews, linearity is the unlock for a specific class of problems that look intractable until you introduce indicator variables. The canonical trick is: define Iₖ = 1 if event k occurs, 0 otherwise. Then E[Iₖ] = P(event k), and E[total count of events] = Σ P(event k). Problems that would require inclusion-exclusion or complicated conditional reasoning collapse to simple probability sums. Interviewers love linearity questions because they distinguish candidates who just memorised formulas from candidates who genuinely understand expectation as a linear operator.
WHEN IT APPEARS IN INTERVIEWS
Constant at Jane Street (their favourite tool), frequent at SIG, Optiver, and Citadel. Problems where the target is a count of events with complicated dependencies are the give-away — any 'expected number of X' question should trigger the linearity reflex.
FIRMS THAT TEST THIS
SAMPLE PROBLEMS
You shuffle n cards labelled 1, 2, …, n. What's the expected number of cards that end up in their own position (matches)?
Let Iₖ = 1 if card k lands in position k. P(Iₖ = 1) = 1/n. E[matches] = Σ E[Iₖ] = n · (1/n) = 1. Surprisingly, the answer is 1 regardless of n.
You shuffle n distinct numbers uniformly at random. An inversion is a pair (i, j) with i < j but aᵢ > aⱼ. Expected number of inversions?
For each pair (i, j), P(inversion) = 1/2 by symmetry. There are C(n, 2) pairs. E[inversions] = C(n, 2) / 2 = n(n-1)/4. Linearity doesn't care that inversions are highly correlated across pairs.
n people check their hats; hats are returned in random order. What's the expected number of people who get their own hat back?
Identical to the matches problem. E[count] = Σ P(person k gets own hat) = n · (1/n) = 1. The classic example interviewers use to teach linearity.
In a random permutation of n elements, a 'record' is a position i where the value is larger than all previous values. What's the expected number of records?
Define Iᵢ = 1 if position i is a record. By symmetry, P(Iᵢ) = 1/i (position i is a record iff its value is the max of the first i, which happens with probability 1/i). E[records] = Σ 1/i = H_n ≈ ln n.
SOLVING STRATEGIES
- ·Whenever you see 'expected number of X', immediately introduce indicator variables Iₖ for each X. This reflex solves most problems in one line.
- ·Don't worry about correlations between indicators. Linearity holds regardless — that's the whole point.
- ·Use symmetry to simplify E[Iₖ] when possible. If events are exchangeable, they all have the same probability.
- ·If the problem involves higher moments (variance, covariance), linearity doesn't give them for free — you need to track correlations explicitly.
- ·Check your answer's limiting behaviour: as n → ∞, does the expected count scale in a way that makes sense?
COMMON VARIATIONS
- ·Expected count of pairs, triples, or k-tuples satisfying some property.
- ·Expected maximum or minimum via linearity + tail probability identity: E[max X] = Σ P(max ≥ k).
- ·Coupon collector variants: expected number of draws to see all coupon types, computed as a sum of geometric expectations.
- ·Graph problems: expected number of edges in a random graph, expected triangles, etc.
FAQ
Expectation is a linear operator on the space of random variables; linearity follows from the integral (or sum) definition. Independence is required for products — E[XY] = E[X]E[Y] only when X and Y are independent — but not for sums.
It doesn't, for sums — ever. But if the problem asks for E[max X], E[X·Y], or variance, you need more than linearity. Linearity is necessary but not sufficient for second-moment questions.
Trigger phrases: 'expected number of', 'expected count of', 'how many on average'. The target is almost always a sum of indicators waiting to be decomposed.
Because candidates who haven't seen linearity explicitly tend to attack these problems with brute-force casework, which blows up combinatorially. Candidates who know the trick solve the same problem in one line. The gap is a clean signal.
RELATED TECHNIQUES
Not ready to sign up? Get 5 hand-picked quant interview problems every week. No spam, unsubscribe any time.
Drill linearity of expectation problems now
400+ problems, adaptive selection, AI-generated alternative explanations. Free tier covers 20 attempts.
Start practicing free