Bonferroni's inequalities

Question

I was recently looking through an introductory probability textbook and encountered the following statement as an exercise to be proved inductively.

$$P(\bigcup_{i=1}^{n}A_i)\ge\sum^n_{i=1}P(A_i)-\sum_{1\lt i\lt j\lt n}P(A_iA_j)$$

The book stated that this was the first in a series of inequalities that give upper and lower bounds for even and odd iterations, until finally giving the inclusion-exclusion principle (an equality) when all terms are included. The first of such inequalities is Boole's inequality. As a method of proof, the book suggested induction with $n$, and additionally suggested the use of Boole's inequality. The book goes on to say, "Continuing like this, show that adding the third sum: $\sum_{i\lt j\lt k}P(A_iA_jA_k)$ gives an upper bound, subtracting the fourth sum gives a lower bound, and so on."

Answer 1

This can be viewed as a combinatorial question, that boils down to the successive partial sums of $k-\binom k 2 + \binom k 3-\binom k 4+\cdots$ alternating in sign. (This can be read off of Pascal's triangle.) Bonferroni's inequalities can be obtained by taking the expectation of the random variable $\chi_{\cup_i A_i} (x)=1-\prod_i (1-\chi_{A_i}(x))$ and comparing it with the expectation of a truncation of the series $$\chi_{\cup_i A_i} (x)=\sum_i \chi_{A_i}(x)-\sum_{i<j} \chi_{A_i}(x)\chi_{A_j}(x)+\sum_{i<j<k} \chi_{A_i}(x)\chi_{A_j}(x)\chi_{A_k}(x)-\cdots\tag{*}$$ that you get by multiplying out the product. (Where $\chi_S(x) = 1$ if $x\in S$ and $0$ otherwise.)

Suppose $x$ is an element of exactly $k$ of the subsets $A_i$, where $k>0$. Then the terms in the above series are $$ \chi_{\cup A_i}(x) =1 = k - \binom k 2 + \binom k 3 - \cdots,$$ but if $k=0$ the terms in the series are $$ \chi_{\cup A_i}(x) = 0 = 0 - \binom 0 2 + \binom 0 3 - \cdots.$$ In either case, when truncated, you get over or under estimates of the untruncated sum: Take an odd number of terms on the right hand side of (*) and you get an overestimate of the left hand side; take an even number of terms and you get an underestimate. Finish the job by integrating this inequality with respect to $x$.