Proof Bonferroni’s Inequality

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.

One Response to “Proof Bonferroni’s Inequality”
  1. It looks like you are a real pro. Did you study about the subject? hrhr

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

  • November 2008
    S M T W T F S
    « Oct   Dec »
%d bloggers like this: