Bonferroni Inequality

137. Bonferroni Inequality

Two Sets

𝑃 (𝑆 \cap 𝑇) \geq 𝑃 (𝑆) + 𝑃 (𝑇) - 1

Proof: Bonferroni Inequality (2 Sets)

Start with union bound:

𝑃 (𝐴^{𝑐} \cup 𝐵^{𝑐}) \leq 𝑃 (𝐴^{𝑐}) + 𝑃 (𝐵^{𝑐})

And De Morgan’s Law:

𝐴^{𝑐} \cup 𝐵^{𝑐} = {(𝐴 \cap 𝐵)}^{𝑐}

Rewrite all terms in terms of probabilities of $𝐴$ and $𝐵$ :

𝑃 (𝐴^{𝑐}) = 1 - 𝑃 (𝐴) 𝑃 (𝐵^{𝑐}) = 1 - 𝑃 (𝐵)

Insert into the union bound:

𝑃 ({(𝐴 \cap 𝐵)}^{𝑐}) \leq (1 - 𝑃 (𝐴)) + (1 - 𝑃 (𝐵))

Use complement again:

1 - 𝑃 (𝐴 \cap 𝐵) \leq 2 - 𝑃 (𝐴) - 𝑃 (𝐵)

Rearrange:

𝑃 (𝐴 \cap 𝐵) \geq 𝑃 (𝐴) + 𝑃 (𝐵) - 1

$𝑛$ Sets

\begin{aligned} 𝑃 (⋂_{𝑖 = 1}^{𝑛} 𝐴_{𝑖}) & \geq \sum_{𝑖 = 1}^{𝑛} 𝐴_{𝑖} - (𝑛 - 1) \\ 𝑃 (𝐴_{1}, \cap \dots \cap 𝐴_{𝑛}) & \geq 𝑃 (𝐴_{1}) + \dots + 𝑃 (𝐴_{𝑛}) - (𝑛 - 1) \end{aligned}

Proof: Bonferroni Inequality ( $𝑛$ Sets)

Start with the union bound

𝑃 (⋃_{𝑖 = 1}^{𝑛} 𝐴_{𝑖}^{𝑐}) \leq \sum_{𝑖 = 1}^{𝑛} 𝑃 (𝐴_{𝑖}^{𝑐})

De Morgan’s Law

⋃_{𝑖 = 1}^{𝑛} 𝐴_{𝑖}^{𝑐} = {(⋂_{𝑖 = 1}^{𝑛} 𝐴_{𝑖})}^{𝑐}

So we can rewrite the LHS as:

𝑃 ({(⋂_{𝑖 = 1}^{𝑛} 𝐴_{𝑖})}^{𝑐})

Rewrite each complement probability

For each $𝑖$ :

𝑃 (𝐴_{𝑖}^{𝑐}) = 1 - 𝑃 (𝐴_{𝑖})

Thus:

𝑃 ({(⋂_{𝑖 = 1}^{𝑛} 𝐴_{𝑖})}^{𝑐}) \leq \sum_{𝑖 = 1}^{𝑛} (1 - 𝑃 (𝐴_{𝑖}))

Use the complement relation $𝑃 (𝐸^{𝑐}) = 1 - 𝑃 (𝐸)$

1 - 𝑃 (⋂_{𝑖 = 1}^{𝑛} 𝐴_{𝑖}) \leq 𝑛 - \sum_{𝑖 = 1}^{𝑛} 𝑃 (𝐴_{𝑖})

Rearrange to obtain the lower bound

Move terms around:

𝑃 (⋂_{𝑖 = 1}^{𝑛} 𝐴_{𝑛}) \geq \sum_{{𝑖 = 1}}^{𝑛} 𝑃 (𝐴_{𝑖}) - (𝑛 - 1)