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: inequality, Probability
0 Comments:
Post a Comment
<< Home