Boole's Inequality

Theorem

Let $\left({\Omega, \Sigma, \Pr}\right)$ be a probability space.

Let $A_1, A_2, \ldots, A_n$ be events in $\Sigma$.

Then:

$\displaystyle \Pr \left({\bigcup_{i=1}^n A_i}\right) \le \sum_{i=1}^n \Pr \left({A_i}\right)$

Proof

A direct consequence of the facts that:

• A Probability Measure is Subadditive;

• The result Finite Union of Sets in Subadditive Function which gives:

$\displaystyle f \left({\bigcup_{i=1}^n A_i}\right) \le \sum_{i=1}^n f \left({A_i}\right)$

for a subadditive function $f$.

$\blacksquare$

Note

This inequality is also known as Union Bound.

Sources

• Geoffrey Grimmett and Dominic Welsh: Probability: An Introduction (1986): $\S 1.11$: Problem $3$