## You are here

HomeBonferroni inequalities

## Primary tabs

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

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

Related:

BrunsPureSieve

Type of Math Object:

Theorem

Major Section:

Reference

## Mathematics Subject Classification

60A99*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff