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."

  • 1
    $\begingroup$ So, what's your question? $\endgroup$ – Taroccoesbrocco Jan 3 '18 at 17:22
  • $\begingroup$ How the main inequality (and the successive inequalities in the series) can be proved inductively $\endgroup$ – BelowAverageIntelligence Jan 3 '18 at 17:26

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.