# Bonferroni inequalities

Let $E(1)$, $E(2),\ldots,E(n)$ be events in a sample space. Define

 $\displaystyle S_{1}:=\sum_{i=1}^{n}\Pr(E(i))$ $\displaystyle S_{2}:=\sum_{i

and for $2,

 $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.

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.

Title Bonferroni inequalities BonferroniInequalities 2013-03-22 14:30:40 2013-03-22 14:30:40 kshum (5987) kshum (5987) 9 kshum (5987) Theorem msc 60A99 BrunsPureSieve union bound