Proof of a Bonferroni inequality

Here is a very enjoyable theorem due to Bonferroni. Let \(n \geq 2 \) and consider the probability triple \( (\Omega, \mathcal{F}, P) \) and a collection of sets of \( \Omega \) in \( \mathcal{F} \) denoted \( ( A_i )_{i=1}^n \). Then the following holds:

Proof

By induction. The case where \(n = 2\) is obvious. Assume the inequality holds up to \(n\) and denote \(B = \bigcup_{i = 1}^n A_i \). Then the base case implies

Using the distributive law, this becomes

which, by Boole’s inequality, is less than or equal to \( \sum_{i=1}^n P(A_{n + 1} \cap A_i) \). So,

by the inductive hypothesis. Simplifying, we note that the term \( \sum_{i=1}^n P(A_{n + 1} \cap A_i) \) is the increment of the sum over \( i < j \) in the inequality, thus resulting in

which was to be proved.

Written on September 2, 2017