Bonferroni inequalities

Primary tabs

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.

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.

Defines:

union bound

Type of Math Object:

Theorem

Major Section:

Reference