Bonferroni inequalities

Let $E(1)$, $E(2),\mathrm{\dots },E(n)$ be events in a sample space. Define

$S_1:={\displaystyle \sum _{i=1}^n}\mathrm{Pr}(E(i))$

and for ,

$$S_k:=\sum \mathrm{Pr}(E(i_1)\cap \mathrm{\cdots }\cap E(i_k))$$

where the summation is taken over all ordered $k$-tuples of distinct integers.

Theorem

For odd $k$, $1\le k\le n$,

$$\mathrm{Pr}(E(1)\cup \mathrm{\cdots }\cup E(n))\le \sum _{j=1}^k{(-1)}^{j+1}{S}_j,$$

and for even $k$, $2\le k\le n$,

$$\mathrm{Pr}(E(1)\cup \mathrm{\cdots }\cup E(n))\ge \sum _{j=1}^k{(-1)}^{j+1}{S}_j,$$

Remark When $k=1$, the Bonferroni inequality is also known as the union bound.When $k=n$, we have an equality, also known as the inclusion-exclusion principle.