# Bonferroni inequalities

Let $E(1)$, $E(2),\mathrm{\dots},E(n)$ be events in a sample space. Define

${S}_{1}:={\displaystyle \sum _{i=1}^{n}}\mathrm{Pr}(E(i))$ | ||

$$ |

and for $$,

$${S}_{k}:=\sum \mathrm{Pr}(E({i}_{1})\cap \mathrm{\cdots}\cap E({i}_{k}))$$ |

where the summation is taken over all ordered $k$-tuples of distinct integers.

For odd $k$, $1\le k\le n$,

$$\mathrm{Pr}(E(1)\cup \mathrm{\cdots}\cup E(n))\le \sum _{j=1}^{k}{(-1)}^{j+1}{S}_{j},$$ |

and for even $k$, $2\le k\le n$,

$$\mathrm{Pr}(E(1)\cup \mathrm{\cdots}\cup E(n))\ge \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 |
---|---|

Canonical name | BonferroniInequalities |

Date of creation | 2013-03-22 14:30:40 |

Last modified on | 2013-03-22 14:30:40 |

Owner | kshum (5987) |

Last modified by | kshum (5987) |

Numerical id | 9 |

Author | kshum (5987) |

Entry type | Theorem |

Classification | msc 60A99 |

Related topic | BrunsPureSieve |

Defines | union bound |