Linearity of expectation for indicator sums
Statement
For any events in a probability space (not necessarily independent), if counts how many of them occur, then .
Why is it true?
It lets us compute the average of a count by adding up individual probabilities one at a time, without ever worrying about how the events interact with each other — the single most useful shortcut in the probabilistic method.
Proof sketch
Write where is if occurs and otherwise. Expectation is itself defined as a sum (or integral) over outcomes weighted by their probability, and this sum is always additive over a finite list of random variables — this is true regardless of whether the variables are independent, since additivity of expectation never uses independence, only that we are summing the same underlying probability measure.
Formally, by additivity of expectation over a finite sum of random variables.
Finally, for any indicator variable, . Substituting this into the sum gives exactly , with no assumption on how the relate to one another.
Topics that use this theorem
Step-by-step proofs
No step-by-step proof yet for this theorem.
References
- Noga Alon, Joel H. Spencer (2016). The Probabilistic Method
- Marcelo Campos, Simon Griffiths, Robert Morris, Julian Sahasrabudhe (2023). Towards fully exponential bounds for the diagonal Ramsey numbers · arXiv:2303.09521 [preprint, not peer-reviewed]
- Reinhard Diestel (2017). Graph Theory