136. Bonferroni Inequality

  1. Two Sets

Proof: Bonferroni Inequality (2 Sets)

  1. Start with union bound:
  1. And De Morgan’s Law:
  1. Rewrite all terms in terms of probabilities of and :

Insert into the union bound:

  1. Use complement again:
  1. Rearrange:
  1. Sets

Proof: Bonferroni Inequality ( Sets)

  1. Start with the union bound
  1. De Morgan’s Law

So we can rewrite the LHS as:

  1. Rewrite each complement probability

For each :

Thus:

  1. Use the complement relation
  1. Rearrange to obtain the lower bound

Move terms around: