|
Let $E(1)$ , $E(2),\ldots, E(n)$ be events in a sample space. Define
and for $2<k\leq n$ , $$ S_k := \sum \Pr(E(i_1)\cap \cdots \cap E(i_k) ) $$ where the summation is taken over all ordered $k$ -tuples of distinct integers.
Theorem
For odd $k$ , $1 \leq k \leq n$ , $$ \Pr(E(1)\cup\cdots\cup E(n)) \leq \sum_{j=1}^k (-1)^{j+1} S_j, $$ and for even $k$ , $2\leq k \leq n$ , $$ \Pr(E(1)\cup\cdots\cup E(n)) \geq \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.
|
