Friday, December 02, 2016

Bonferroni Inequality and how to think about it


Bonferroni Inequality provides a lower bound for intersection of sets in terms of the individual probability of sets. For $2$ sets. It says that $P(A_1 \cap A_2) \ge P(A_1)+P(A_2)-1$ for two sets $P(A_1 \cap A_2 \cdots \cap A_n) \ge P(A_1)+P(A_2)+\cdots+P(A_n)-n+1$ for n sets Main Idea: The union of sets is always smaller than the sum of the individual sets. You can basically take this as an axiom. We start with $P(A \cup B)= P(A)+P(B)-P(A \cap B)$ $\Rightarrow P(A \cap B)= P(A)+P(B)-P(A \cup B)$ as $P(A \cup B) \le 1$ $\Rightarrow P(A \cap B) \ge P(A)+P(B)-1$ This can also be written as $P(A \cap B) \ge P(A)+P(B)-2+1$ Let's generalize it for $n$ sets. Notice that $P(A_1 \cap A_2 \cap \ldots \cap A_n)=P((A_1^c \cup A_2^c \cup\ldots \cup A_n^c)^c) = 1-P(A_1^c \cup A_2^c \cup \cdots \cup A_n^c)$ $\Rightarrow 1-P(A_1^c \cup A_2^c \cup \cdots \cup A_n^c) =P(A_1 \cap A_2 \cap \ldots \cap A_n)$ $\Rightarrow P(A_1^c \cup A_2^c \cup \cdots \cup A_n^c) =1-P(A_1 \cap A_2 \cap \ldots \cap A_n)$ Lets start with the idea that probability of union of sets is always smaller than the sum of probabilities of individual sets. $\Rightarrow P(A_1^c \cup A_2^c \cup \ldots \cup A_n^c) \le P(A_1^c)+P(A_2^c)+\ldots+P(A_n^c)$ $\Rightarrow 1-P(A_1 \cap A_2 \ldots \cap A_n) \le 1-P(A_1)+1-P(A_2)+\ldots+1-P(A_n)$ $\Rightarrow 1-P(A_1 \cap A_2 \ldots \cap A_n) \le n-P(A_1)-P(A_2)-\ldots -P(A_n)$ $\Rightarrow P(A_1)+P(A_2)+\ldots+P(A_n)\le P(A_1 \cap A_2 \ldots \cap A_n)-1+n$ $\Rightarrow P(A_1)+P(A_2)+\ldots+P(A_n)-n+1\le P(A_1 \cap A_2 \ldots \cap A_n)$ $\Rightarrow P(A_1 \cap A_2 \ldots \cap A_n)\ge P(A_1)+P(A_2)+\ldots+P(A_n)-n+1$

Labels: ,

0 Comments:

Post a Comment

<< Home

Site Meter