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<j}\Pr(E(i)\cap E(j)),$

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.

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.