Bonferroni Inequality

Bonferroni inequality states that the probability of intersections between  ‘n’ independent events is always greater than or equal to the difference between the sum of the events and 1 less than the total number of events.

Mathematically, it is written as

If ‘A₁,’ ‘A₂,’ …, ‘A_n’ are the independent events in a probability space (X, p) and A_i = A₁ ∪ A₂ ∪ … ∪ A_n, then 

${P\left( \cap ^{n}_{i=1}A_{i}\right) \geq \sum ^{n}_{i=1}P\left( A_{i}\right) -\left( n-1\right)}$

Proof

Let us prove Bonferroni’s inequality using mathematical induction.

Base Step

For n = 1, P(A₁) ≥ 1 – 1 + P(A₁) = P(A₁), which is true.

For n = 2, by De Morgan’s law, P((A₁ ∩ A₂)^c) = P(A₁^c ∪ A₂^c) ≤ P(A₁^c) + P(A₂^c)

⇒ P((A₁ ∩ A₂)^c) ≤ P(A₁^c) + P(A₂^c)

⇒ 1 – P(A₁ ∩ A₂) ≤ 1 – P(A₁) + 1 – P(A₂)

⇒ 1 – P(A₁ ∩ A₂) ≤ 2 – P(A₁) – P(A₂)

⇒ P(A₁ ∩ A₂) ≥ P(A₁) + P(A₂) – (2 – 1), which is true.

Inductive Step

Let us assume Bonferroni’s inequality holds for n = m.

We have

${P\left( \cap ^{m}_{i=1}A_{i}\right) \geq \sum ^{m}_{i=1}P\left( A_{i}\right) -\left( m-1\right)}$ …..(i)

Now, assuming n = m + 1, we get

${P\left( \cap ^{m+1}_{i=1}A_{i}\right)}$

= ${P\left[ \left( \cap ^{m}_{i=1}A_{i}\right) \cap A_{m+1}\right]}$

= ${P\left( \cap ^{m} _{i=1}A_{i}\right) +P\left( A_{m+1}\right) -P\left[ \left( \cap ^{m}_{i=1}A_{i}\right) \cup A_{m+1}\right]}$

From (i), we have

${P\left( \cap ^{m+1}_{i=1}A_{i}\right)\geq \sum ^{m}_{i=1}P\left( A_{i}\right) -m+1+P\left( A_{m+1}\right) -P\left[ \left( \cap ^{m}_{i=1}A_{i}\right) \cup A_{m+1}\right]}$

⇒ ${P\left( \cap ^{m+1}_{i=1}A_{i}\right)\geq \sum ^{m+1}_{i=1}P\left( A_{i}\right) -m+1-P\left[ \left( \cap ^{m}_{i=1}A_{i}\right) \cup A_{m+1}\right]}$ …..(ii)

By the definition of probability, the last term of (ii) can not exceed 1.

Thus, ${P\left( \cap ^{m+1}_{i=1}A_{i}\right)\geq \sum ^{m+1}_{i=1}P\left( A_{i}\right) -m+1-1}$

⇒ ${P\left( \cap ^{m+1}_{i=1}A_{i}\right)\geq \sum ^{m+1}_{i=1}P\left( A_{i}\right) -\left[ \left( m+1\right) -1\right]}$, which shows that if the statement holds for n = m, then it is also true for n = m + 1.

Thus, Bonferroni’s inequality is proved.

Alternative Form

Bonferroni inequality in the generalized form states that if ‘A₁,’ ‘A₂,’ …, ‘A_n’ are random events in a probability space (X, p) and A_i = A₁ ∪ A₂ ∪ … ∪ A_n, then the upper and lower bounds for P(A) are:

${P\left( A_{i}\right) \leq \sum ^{m}_{k=1}\left( -1\right) ^{k-1}S_{k}}$, for any odd ‘m’

${P\left( A_{i}\right) \geq \sum ^{m}_{k=1}\left( -1\right) ^{k-1}S_{k}}$, for any even ‘m’

When ‘A_i’ and ‘A_j’ are disjoint sets for all ‘i’ and ‘j,’ the inequality becomes equality.

Solved Example