MathLabs
TheoremProved

Linearity of expectation for indicator sums

Statement

For any events A1,…,AmA_1,\dots,A_m in a probability space (not necessarily independent), if X=∑i=1m1[Ai]X = \sum_{i=1}^m \mathbb{1}[A_i] counts how many of them occur, then E[X]=∑i=1mPr⁡[Ai]\mathbb{E}[X] = \sum_{i=1}^m \Pr[A_i].

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 X=∑i=1m1[Ai]X = \sum_{i=1}^m \mathbb{1}[A_i] where 1[Ai]\mathbb{1}[A_i] is 11 if AiA_i occurs and 00 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, E[X]=E[∑i=1m1[Ai]]=∑i=1mE[1[Ai]]\mathbb{E}[X] = \mathbb{E}\left[\sum_{i=1}^m \mathbb{1}[A_i]\right] = \sum_{i=1}^m \mathbb{E}[\mathbb{1}[A_i]] by additivity of expectation over a finite sum of random variables.

Finally, for any indicator variable, E[1[Ai]]=1⋅Pr⁡[Ai]+0⋅Pr⁡[Ai‾]=Pr⁡[Ai]\mathbb{E}[\mathbb{1}[A_i]] = 1 \cdot \Pr[A_i] + 0 \cdot \Pr[\overline{A_i}] = \Pr[A_i]. Substituting this into the sum gives exactly E[X]=∑i=1mPr⁡[Ai]\mathbb{E}[X] = \sum_{i=1}^m \Pr[A_i], with no assumption on how the AiA_i relate to one another.

Topics that use this theorem

Step-by-step proofs

No step-by-step proof yet for this theorem.

References

  1. Noga Alon, Joel H. Spencer (2016). The Probabilistic Method
  2. 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]
  3. Reinhard Diestel (2017). Graph Theory