Bonferroni and Boole

In it's simplest form, Bonferroni's inequality states:

P(A ∩ B) ≥ P(A) + P(B) - 1

This result is both self-evident and largely useless. The self-evident part comes from the fact that

1 ≥ P(A ∪ B) = P(A) + P(B) - P(A ∩ B)

Just flip the 1 and the P(A ∩ B) to the other sides of the inequality.

The largely useless part comes from the fact that, unless A and B are pretty likely, the bound is negative and any probability is lower-bounded by a negative number.

Still, it's a named result. So I have dutifully logged it.

However, while that's what gets mentioned in most basic probability courses, there's more to it than that. The Bonferroni bound actually applies to any number of sets and, as the number of sets goes up, the number of terms increases, giving a convergent sequence of upper and lower bounds.

Boole's Inequality states that P(∪A_i) ≤ ∑P(A_i) for countable unions of {A_i}. This can be proved fairly readily either with or without induction directly from the Borel and Kolmogorov axioms. Bonferroni built a framework which started with that result as a special case, but then, by considering successively complex intersections, created general upper and lower bounds for finite unions that converge to equality.

Let



and, in general



Basically, S_k is the sum of the probabilities of all intersections of k sets from {A_i}. Then, for odd k we have an upper bound on the union:



and for even k we get a lower bound:



Note that when k = 1, we have Boole's inequality and when k = n, equality holds giving us the inclusion-exclusion principle. Going back to n = 2, we get the following two bounds:

k = 1: P(A ∪ B) ≤ P(A) + P(B) Boole's inequality.

k = 2: P(A ∪ B) = P(A) + P(B) - P(A ∩ B) Exclusion-inclusion principal on two sets.

Combine them and you get the silly result quoted up top. As noted, for small values of n, this is something that can be easily worked out by hand without a unifying formula. However, the fact that it generalizes to any value of n, including countably infinite sets, and the bounds always converge to equality makes it an elegant statement of a significant and less than obvious result. I think texts should stop attributing the n = 2 result to Bonferroni. It makes him look like a total fraud when he actually did some pretty fine work.