Linearity of expectation
PROB · Chapter 39 min readAsked at Jane Street, Optiver, SIG, Five Rings
0:56The lesson in a minutePremium
The key idea, drawn and talked through in a short video before you read. Lesson videos come with Premium.
Start the 7-day free trialUnlockAfter this lesson you should be able to
- State linearity of expectation and explain why independence is not required.
- Decompose a complicated count into a sum of indicator variables.
- Use the method on problems where writing the distribution down is hopeless.
The expectation of a sum is the sum of the expectations – always, whether or not the terms are independent. Almost every hard counting-flavoured probability question in a quant interview becomes easy the moment you write the quantity as a sum of indicators and apply this.
Equation 3.1
The statement
For any random variables on the same probability space, and any constants :
- Any random variable. No independence assumption.
- The expectation of the -th term, computed on its own.
Equation 3.2
With constants
Why independence is irrelevant here. Expectation is an integral, and integration is linear. sums over the joint distribution; splitting that sum into an part and a part only needs each marginal, never how they move together. Dependence changes where the mass sits jointly, not the marginal averages. This is exactly why variance behaves differently: carries a covariance term, because squaring mixes the two variables together.
| Identity | Needs independence? |
|---|---|
| No – always true | |
| Yes (uncorrelated suffices) | |
| Yes (uncorrelated suffices) | |
| Never true in general – see Jensen |
Proposition 3.4
The indicator method
To find the expected number of things with some property, define when the -th thing has the property and 0 otherwise. Then the count is , and because where is the event that item has the property, you get . You never need the distribution of .
Holds when
- The property must be checkable for each item separately.
- The items may overlap, interact or be strongly dependent – it does not matter.
Derivation 3.5
Why an indicator’s expectation is a probability
Expectation of a two-valued variable, straight from the definition.
Example 3.6
The tournament question
A single-elimination tournament starts with equally skilled teams. Each round pairs the surviving teams at random, with a random bye when the count is odd. Two particular teams, A and B, are in the draw. What is the probability they play each other at some point? (A question publicly reported from Five Rings interviews.)
Show the worked solutionHide the worked solution
Worked solution
- Formula
- Substitute
- SolveAn indicator. Its expectation is therefore exactly the probability we want.
- Every game eliminates exactly one team, and all but the winner are eliminated.
- By symmetry every unordered pair is equally likely to be the one playing.
- Answer
Sanity check. With the answer is 1: they must play. With it is , matching the casework answer of .
The rest of this lesson is in Premium
You have read the opening. 11 more sections follow, including 5 worked examples and 3 quick checks.
Nothing is charged for 7 days, and you can cancel before then. Not ready for a trial? A free account, with no card, saves your progress and opens the free questions, the drills and a mock paper. Or read Arithmetic that survives a clock in full, free.