Bonferroni inequalities

Let ${𝐴 𝑖} \subseteq F$ be events and

𝑆 1 = 𝑛 \sum 𝑖 = 1 ℙ (𝐴 𝑖), 𝑆 2 = \sum 1 \leq 𝑖 1 < 𝑖 2 \leq 𝑛 ℙ (𝐴 𝑖 1 \cap 𝐴 𝑖 2), ⋮ 𝑆 𝑘 = \sum 𝑖 \leq 𝑖 1 < \dots < 𝑖 𝑘 \leq 𝑛 ℙ (𝐴 𝑖 1 \cap \dots \cap 𝐴 𝑖 𝑘)

for $𝑘 = 1, \dots, 𝑛$ . Then for odd $𝐾 \leq 𝑛$

𝐾 \sum 𝑗 = 1 (- 1) 𝑗 - 1 𝑆 𝑗 \geq ℙ (𝑛 ⋃ 𝑖 = 1 𝐴 𝑖) = 𝑛 \sum 𝑗 = 1 (- 1) 𝑗 - 1 𝑆 𝑗

and for even $𝐾 \leq 𝑛$ prob

𝐾 \sum 𝑗 = 1 (- 1) 𝑗 - 1 𝑆 𝑗 \leq ℙ (𝑛 ⋃ 𝑖 = 1 𝐴 𝑖) = 𝑛 \sum 𝑗 = 1 (- 1) 𝑗 - 1 𝑆 𝑗

Proof

proof