Boole's inequality

Proof by induction

For finite collections of events, Boole's inequality can be proved by induction. First, for any event ${\displaystyle A_{1}}$, one trivially has

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

Next, assume that the inequality holds for any collection of ${\displaystyle n}$ events, and consider n+1 events ${\displaystyle A_{1},\ldots ,A_{n}.}$ By the induction hypothesis, we have

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

By applying the equality ${\displaystyle \mathbb {P} (A\cup B)=\mathbb {P} (A)+\mathbb {P} (B)-\mathbb {P} (A\cap B),}$ to ${\displaystyle A=A_{1}\cup \cdots \cup A_{n}}$ and ${\displaystyle B=A_{n+1},}$ we get

${\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, by the first axiom of probability,

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

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}).}$

The countable version of Boole's inequality can then be deduced from its finite version by taking n to infinity and using the continuity from below of probability measures.

Proof without using induction

Let events ${\displaystyle A_{1},A_{2},A_{3},\dots }$in our probability space be given. The countable additivity of the measure ${\displaystyle \mathbb {P} }$ states that if ${\displaystyle B_{1},B_{2},B_{3},\dots }$ are pairwise disjoint events, then

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

Set

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

Then ${\displaystyle B_{1},B_{2},B_{3},\dots }$ are pairwise disjoint. We claim that:

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

One inclusion is clear. Indeed, since ${\displaystyle B_{i}\subset A_{i}}$ for all i, thus ${\displaystyle \bigcup _{i=1}^{\infty }B_{i}\subset \bigcup _{i=1}^{\infty }A_{i}}$.

For the other inclusion, let ${\displaystyle x\in \bigcup _{i=1}^{\infty }A_{i}}$ be given. Write ${\displaystyle k}$ for the minimum positive integer such that ${\displaystyle x\in A_{k}}$. Then ${\displaystyle x\in A_{k}-\bigcup _{j=1}^{k-1}A_{j}=B_{k}}$. Thus ${\displaystyle x\in \bigcup _{i=1}^{\infty }B_{i}}$. Therefore ${\displaystyle \bigcup _{i=1}^{\infty }A_{i}\subset \bigcup _{i=1}^{\infty }B_{i}}$.

Therefore

${\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}),}$

where the last inequality holds because ${\displaystyle B_{i}\subset A_{i}}$ implies that ${\displaystyle \mathbb {P} (B_{i})\leq \mathbb {P} (A_{i}),}$ for all i.

Proof for odd K

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}{\Big (}{L-1 \choose j-1}+{L-1 \choose j}{\Big )}\mathbb {P} (E)}$

which telescopes to

${\displaystyle {\Big (}1+{L-1 \choose K}{\Big )}\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} {\Big (}\bigcup _{i=1}^{n}A_{i}{\Big )}}$

The proof for even ${\displaystyle K}$ is nearly identical.

Example

Suppose that you are estimating five 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 other words, 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.