Q.7.6 - A First Course in Probability

Question

Let $A_1,A_{2,\dots ,}{A}_n$ be events, and let $N$ denote the number of them that occur. Also, let $I=1$ if all of these events occur, and let it be $0$ otherwise. Prove Bonferroni’s inequality, namely,

$P(A_1\cdots A_n)\ge \sum _{i=1}^{n}P\left(A_i\right)-(n-1)$

Hint: Argue first that $N\le n-1+I$

Step-by-Step Solution

Answer

By using induction we prove Bonferroni's inequality.

If all the events $A_i,i=1,2,\dots ,n$ occur, then $N=n \text{ and }I=1$.

While on the other side, if all the events $A_i,i=1,2,\dots ,n$ do not occur, then $N<n\text{ and }I=0$

Step 1: Given Information

Let A$1$,A$2$,...,An be events, and let N denote the number of them that occur.

Given the values as follow,

$P(A_1\cdots A_n)\ge \sum _{i=1}^{n}P\left(A_i\right)-(n-1)$

N$\le$ n − 1 + $1$. 

Step 2: Define the indicator variable

$\text{ Let }N\text{ represents the number of events }{A}_1,A_2,\dots ,A_n\text{ that occur and let indicator variable }I\text{ be defined as: }$

$I=\left\{\begin{array}{l}1,\text{ if }{A}_1{A}_2\cdots A_n\text{ occurs }\\ 0,\text{ if }{A}_1{A}_2\cdots A_n\text{ does not occur }\end{array}\right.$

$\text{Further, if indicator variables}{I}_j,j=1,2,\dots ,n\text{, are defined as:}$

$I_j=\left\{\begin{array}{l}1,\text{ if }{A}_j\text{ occurs }\\ 0,\text{ if }{A}_j\text{ does not occur }\end{array}\right.$

Then,

$N=\sum _{j=1}^n{I}_j$

Step 3: Representation of variables

If all of the events $A_i,i=1,2,\dots ,n$occur, then$N=n and I=1$

and in that case, variable $N$ can be represented as

$N=n-1+1=n-1+I$

On the other hand, if all of the events $A_i,i=1,2,\dots ,n$ do not occur, then

$N<n\text{ and }I=0$

and in that case

$N\le n-1+0=n-1+I.$

$\text{Hence,}N\le n-1+I$

Step 4:Applying induction to prove Bonferroni's inequality

Now, use induction to prove Bonferroni's inequality. 

The first case is $n=1$, which is the trivial statement, since

$P\left(A_1\right)=P\left(A_1\right)$

Let's take the second case.

In second case it is $n=2$ since $1\ge P\left(A_1\cup A_2\right)=P\left(A_1\right)+P\left(A_2\right)-P\left(A_1{A}_2\right)$.

Here, we have $P\left(A_1{A}_2\right)\ge P\left(A_1\right)+P\left(A_2\right)-1$

Therefore, the statement is true.

From the above steps, we obtain that, for events $A_1,A_2,\dots ,A_n$, we have

$P\left(A_1\cdots A_n\right)\ge \sum _{i=1}^n P\left(A_i\right)-(n-1)$

Let's prove the desired statement for $n+1$.

Therefore, consider the events $A_1,A_2,\dots ,A_n,A_{n+1}$. Because $A_1,A_2,\dots ,A_{n-1},A_n\cap A_{n+1}$ is a list of $n$ events.

Step 5: Applying Inductive Hypothesis

$P\left(A_1{A}_2\cdots A_n{A}_{n+1}\right)=P\left(A_1\cap \cdots A_{n-1}\cap A_n\cap A_{n+1}\right)$$=P{\left(A_1{A}_2\cdots A_{n-1}\left(A_n\cap A_{n+1}\right)\right)}^{\text{inductive hypothesis }}\ge P\left(A_1\right)+\cdots +P\left(A_{n-1}\right)+P\left(A_n\cap A_{n+1}\right)-(n-1)$

But, since the statement is true for $n=2$, we have that:

$P\left(A_n\cap A_{n+1}\right)\ge P\left(A_n\right)+P\left(A_{n+1}\right)-1$

Therefore, we can concluded that

$P\left(A_1{A}_2\cdots A_n{A}_{n+1}\right)\ge P\left(A_1\right)+\cdots +P\left(A_{n-1}\right)+\left[P\left(A_n\right)+P\left(A_{n+1}\right)-1\right]-(n-1)$

$=P\left(A_1\right)+\cdots +P\left(A_{n-1}\right)+P\left(A_n\right)+P\left(A_{n+1}\right)-n$

$=P\left(A_1\right)+\cdots +P\left(A_{n-1}\right)+P\left(A_n\right)+P\left(A_{n+1}\right)-\left(\right(n+1)-1)$

Step 6: Final Answer

If all of the events $A_i,i=1,2,\dots ,n$ occur, then

$N=n$  and  $I=1$,

while on the other side, if all of the events $A_i,i=1,2,\dots ,n$ do not occur, then

$N<n\text{ and }I=0$

Therefore, $N\le n-1+I$