3.4Linearity of expectation and indicator variables
The idea
Linearity of expectation says the average of a sum is the sum of the averages, even when the pieces depend on each other. Write a count as a sum of 0/1 indicators and add their probabilities.
Think of it like this: To estimate how many of your friends are at a party, add up the chance each one shows up; you need not know how they influence each other.
Why it exists
It solves in one line problems that look like they need long counting: expected keys per slot, triangles in a random graph, fixed points.
How it works
- Define an indicator Iᵢ for each "thing" that may happen (1 if it does, 0 if not).
- The count is X = I₁ + I₂ + …
- E[Iᵢ] = P(Iᵢ = 1).
- E[X] = Σ P(Iᵢ = 1).
- No independence is needed.
Worked example: GATE 2013: random graph on 8 vertices, edge probability 1/2; expected triangles
There are C(8, 3) = 56 triples; each is a triangle with probability (1/2)³ = 1/8. E = 56/8 = 7. The lab simulates this and gets close to 7.
Now play with it
- →Choose "triangles" and run 10000 simulations.
- →Try "fixed points of a permutation": the exact answer is 1, whatever the size.
Indicator trick: write X as a sum of 0/1 indicators I₁ + I₂ + …, so E[X] = ΣP(Iᵢ = 1). There are C(8,3) = 56 triples; each is a triangle with probability (1/2)^3 = 1/8. So 56/8 = 7. The indicators need not be independent: linearity of expectation always holds.
Check yourself
n keys are hashed uniformly into m slots. What is the expected number of keys in slot 1?
Exam notes (the dense version)
E[X + Y] = E[X] + E[Y] always, independent or not. To count something that is a sum of yes/no events, write X = ΣIᵢ with indicators and use E[X] = ΣP(Iᵢ = 1): fixed points of a random permutation, empty bins, triangles in a random graph, keys per hash slot (n/m).
Previous year questions: Random Variables, Expectation & Variance (11)
PYQs are grouped by topic, so this is the full set for Random Variables, Expectation & Variance; try the ones that match this subtopic. Open all 11 on the topic page.