Proof using induction edit

Boole's inequality may be proved for finite collections of ${\displaystyle n}$  events using the method of induction.

For the ${\displaystyle n=1}$  case, it follows that

${\displaystyle \mathbb {P} (A_{1})\leq \mathbb {P} (A_{1}).}$ 

For the case ${\displaystyle n}$ , we have

${\displaystyle {\mathbb {P} }\left(\bigcup _{i=1}^{n}A_{i}\right)\leq \sum _{i=1}^{n}{\mathbb {P} }(A_{i}).}$ 

Since ${\displaystyle \mathbb {P} (A\cup B)=\mathbb {P} (A)+\mathbb {P} (B)-\mathbb {P} (A\cap B),}$  and because the union operation is associative, we have

${\displaystyle \mathbb {P} \left(\bigcup _{i=1}^{n+1}A_{i}\right)=\mathbb {P} \left(\bigcup _{i=1}^{n}A_{i}\right)+\mathbb {P} (A_{n+1})-\mathbb {P} \left(\bigcup _{i=1}^{n}A_{i}\cap A_{n+1}\right).}$ 

Since

${\displaystyle {\mathbb {P} }\left(\bigcup _{i=1}^{n}A_{i}\cap A_{n+1}\right)\geq 0,}$ 

by the first axiom of probability, we have

${\displaystyle \mathbb {P} \left(\bigcup _{i=1}^{n+1}A_{i}\right)\leq \mathbb {P} \left(\bigcup _{i=1}^{n}A_{i}\right)+\mathbb {P} (A_{n+1}),}$ 

and therefore

${\displaystyle \mathbb {P} \left(\bigcup _{i=1}^{n+1}A_{i}\right)\leq \sum _{i=1}^{n}\mathbb {P} (A_{i})+\mathbb {P} (A_{n+1})=\sum _{i=1}^{n+1}\mathbb {P} (A_{i}).}$ 

Proof without using induction edit

For any events in ${\displaystyle A_{1},A_{2},A_{3},\dots }$ in our probability space we have

${\displaystyle \mathbb {P} \left(\bigcup _{i}A_{i}\right)\leq \sum _{i}\mathbb {P} (A_{i}).}$ 

One of the axioms of a probability space is that if ${\displaystyle B_{1},B_{2},B_{3},\dots }$  are disjoint subsets of the probability space then

${\displaystyle \mathbb {P} \left(\bigcup _{i}B_{i}\right)=\sum _{i}\mathbb {P} (B_{i});}$ 

this is called countable additivity.

If we modify the sets ${\displaystyle A_{i}}$ , so they become disjoint,

${\displaystyle B_{i}=A_{i}-\bigcup _{j=1}^{i-1}A_{j}}$ 

we can show that

${\displaystyle \bigcup _{i=1}^{\infty }B_{i}=\bigcup _{i=1}^{\infty }A_{i}.}$ 

by proving both directions of inclusion.

Suppose ${\displaystyle x\in \bigcup _{i=1}^{\infty }A_{i}}$ . Then ${\displaystyle x\in A_{k}}$  for some minimum ${\displaystyle k}$  such that ${\displaystyle i<k\implies x\notin A_{i}}$ . Therefore ${\displaystyle x\in B_{k}=A_{k}-\bigcup _{j=1}^{k-1}A_{j}}$ . So the first inclusion is true: ${\displaystyle \bigcup _{i=1}^{\infty }A_{i}\subset \bigcup _{i=1}^{\infty }B_{i}}$ .

Next suppose that ${\displaystyle x\in \bigcup _{i=1}^{\infty }B_{i}}$ . It follows that ${\displaystyle x\in B_{k}}$  for some ${\displaystyle k}$ . And ${\displaystyle B_{k}=A_{k}-\bigcup _{j=1}^{k-1}A_{j}}$  so ${\displaystyle x\in A_{k}}$ , and we have the other inclusion: ${\displaystyle \bigcup _{i=1}^{\infty }B_{i}\subset \bigcup _{i=1}^{\infty }A_{i}}$ .

By construction of each ${\displaystyle B_{i}}$ , ${\displaystyle B_{i}\subset A_{i}}$ . For ${\displaystyle B\subset A,}$  it is the case that ${\displaystyle \mathbb {P} (B)\leq \mathbb {P} (A).}$ 

So, we can conclude that the desired inequality is true:

${\displaystyle \mathbb {P} \left(\bigcup _{i}A_{i}\right)=\mathbb {P} \left(\bigcup _{i}B_{i}\right)=\sum _{i}\mathbb {P} (B_{i})\leq \sum _{i}\mathbb {P} (A_{i}).}$ 

Boole's inequality may be generalized to find upper and lower bounds on the probability of finite unions of events.^[2] These bounds are known as Bonferroni inequalities, after Carlo Emilio Bonferroni; see Bonferroni (1936).

Let

${\displaystyle S_{1}:=\sum _{i=1}^{n}{\mathbb {P} }(A_{i}),\quad S_{2}:=\sum _{1\leq i_{1}<i_{2}\leq n}{\mathbb {P} }(A_{i_{1}}\cap A_{i_{2}}),\quad \ldots ,\quad S_{k}:=\sum _{1\leq i_{1}<\cdots <i_{k}\leq n}{\mathbb {P} }(A_{i_{1}}\cap \cdots \cap A_{i_{k}})}$ 

for all integers k in {1, ..., n}.

Then, when ${\displaystyle K\leq n}$  is odd:

${\displaystyle \sum _{j=1}^{K}(-1)^{j-1}S_{j}\geq \mathbb {P} \left(\bigcup _{i=1}^{n}A_{i}\right)=\sum _{j=1}^{n}(-1)^{j-1}S_{j}}$ 

holds, and when ${\displaystyle K\leq n}$  is even:

${\displaystyle \sum _{j=1}^{K}(-1)^{j-1}S_{j}\leq \mathbb {P} \left(\bigcup _{i=1}^{n}A_{i}\right)=\sum _{j=1}^{n}(-1)^{j-1}S_{j}}$ 

holds.

The equalities follow from the inclusion–exclusion principle, and Boole's inequality is the special case of ${\displaystyle K=1}$ .

Proof for odd K edit

Let ${\displaystyle E=\bigcap _{i=1}^{n}B_{i}}$ , where ${\displaystyle B_{i}\in \{A_{i},A_{i}^{c}\}}$  for each ${\displaystyle i=1,\dots ,n}$ . These such ${\displaystyle E}$  partition the sample space, and for each ${\displaystyle E}$  and every ${\displaystyle i}$ , ${\displaystyle E}$  is either contained in ${\displaystyle A_{i}}$  or disjoint from it.

If ${\displaystyle E=\bigcap _{i=1}^{n}A_{i}^{c}}$ , then ${\displaystyle E}$  contributes 0 to both sides of the inequality.

Otherwise, assume ${\displaystyle E}$  is contained in exactly ${\displaystyle L}$  of the ${\displaystyle A_{i}}$ . Then ${\displaystyle E}$  contributes exactly ${\displaystyle \mathbb {P} (E)}$  to the right side of the inequality, while it contributes

${\displaystyle \sum _{j=1}^{K}(-1)^{j-1}{L \choose j}\mathbb {P} (E)}$ 

to the left side of the inequality. However, by Pascal's rule, this is equal to

${\displaystyle \sum _{j=1}^{K}(-1)^{j-1}\left({L-1 \choose j-1}+{L-1 \choose j}\right)\mathbb {P} (E)}$ 

which telescopes to

${\displaystyle \left(1+{L-1 \choose K}\right)\mathbb {P} (E)\geq \mathbb {P} (E)}$ 

Thus, the inequality holds for all events ${\displaystyle E}$ , and so by summing over ${\displaystyle E}$ , we obtain the desired inequality:

${\displaystyle \sum _{j=1}^{K}(-1)^{j-1}S_{j}\geq \mathbb {P} \left(\bigcup _{i=1}^{n}A_{i}\right)}$ 

The proof for even ${\displaystyle K}$  is nearly identical.^[3]

Example edit

Suppose that you are estimating 5 parameters based on a random sample, and you can control each parameter separately. If you want your estimations of all five parameters to be good with a chance 95%, what should you do to each parameter?

Tuning each parameter's chance to be good to within 95% is not enough because "all are good" is a subset of each event "Estimate i is good". We can use Boole's Inequality to solve this problem. By finding the complement of event "all five are good", we can change this question into another condition:

P( at least one estimation is bad) = 0.05 ≤ P( A₁ is bad) + P( A₂ is bad) + P( A₃ is bad) + P( A₄ is bad) + P( A₅ is bad)

One way is to make each of them equal to 0.05/5 = 0.01, that is 1%. In another word, you have to guarantee each estimate good to 99%( for example, by constructing a 99% confidence interval) to make sure the total estimation to be good with a chance 95%. This is called the Bonferroni Method of simultaneous inference.

• Diluted inclusion–exclusion principle
• Schuette–Nesbitt formula
• Boole–Fréchet inequalities
• Probability of the union of pairwise independent events

• Bonferroni, Carlo E. (1936), "Teoria statistica delle classi e calcolo delle probabilità", Pubbl. D. R. Ist. Super. Di Sci. Econom. E Commerciali di Firenze (in Italian), 8: 1–62, Zbl 0016.41103
• Dohmen, Klaus (2003), Improved Bonferroni Inequalities via Abstract Tubes. Inequalities and Identities of Inclusion–Exclusion Type, Lecture Notes in Mathematics, vol. 1826, Berlin: Springer-Verlag, pp. viii+113, ISBN 3-540-20025-8, MR 2019293, Zbl 1026.05009
• Galambos, János; Simonelli, Italo (1996), Bonferroni-Type Inequalities with Applications, Probability and Its Applications, New York: Springer-Verlag, pp. x+269, ISBN 0-387-94776-0, MR 1402242, Zbl 0869.60014
• Galambos, János (1977), "Bonferroni inequalities", Annals of Probability, 5 (4): 577–581, doi:10.1214/aop/1176995765, JSTOR 2243081, MR 0448478, Zbl 0369.60018
• Galambos, János (2001) [1994], "Bonferroni inequalities", Encyclopedia of Mathematics, EMS Press

This article incorporates material from Bonferroni inequalities on PlanetMath, which is licensed under the Creative Commons Attribution/Share-Alike License.