Proof Bonferroni’s Inequality

Posted on November 6, 2008. Filed under: Proofs, OR Resources, School | Tags: Bonferroni's Inequality, proof |

Let $E_s$ be an event that occurs with probability $1-\alpha_s$ for $s=1,2,...,k$ . Then $P(\bigcap_{s=1}^k E_s) \geq 1- \sum_{s=1}^k \alpha_s$ where $\bigcap_{s=1}^k E_s$ is the intersection of non-independent events $E_1, E_2, ..., E_k$ .

Proof by induction on n

Base case, $n=2$

$P(E_1 \cup E_2)= P(E_1) + P(E_2) - P(E_1 \cap E_2) \leq 1$

By additivity law and probability axiom

$P(E_1 \cap E_2) \geq P(E_1) + P(E_2) -1$
$\geq (1-\alpha_1)+(1-\alpha_2)-1$
$\geq (1-\alpha_1 - \alpha_2)$

Inductive hypothesis

Suppose relation is true for $n=k-1$ , that is

$P(\bigcap_{s=1}^{k-1}E_s) \geq 1- \sum_{s=1}^{k}\alpha_s$

Inductive Step

Let $A = {\bigcap_{s=1}^{k-1}E_s}$ . Then $P(A) = 1-\sum_{s=1}^{k-1}\alpha_s$

$P(\bigcap_{s=1}^{k}E_s) = P(A\cap E_k)$
$\geq P(A) + P(E_k)-1$
$\geq \displaystyle 1- \sum_{s=1}^{k-1}\alpha_s + (1-\alpha_k) - 1$
$\geq \displaystyle1- \sum_{s=1}^{k-1}\alpha_s -\alpha_k$
$\geq \displaystyle1- \sum_{s=1}^{k}\alpha_s$

as required.

Make a Comment

S	M	T	W	T	F	S
« Oct				Dec »
						1
2	3	4	5	6	7	8
9	10	11	12	13	14	15
16	17	18	19	20	21	22
23	24	25	26	27	28	29
30

Proof Bonferroni’s Inequality

Proof by induction on n

Make a Comment: ( None so far )

Tags

Tweet Tweet

Favourite Posts

Categories