The union bound, also known as Boole’s inequality, says that for a countable set of events, the probability that at least one of the events happens is not greater than the sum of the probabilities of the individual events:
Theorem (Union bound): For a countable set of events \(A_1, A_2, A_3, \ldots\),
\[\Pr \left(\bigcup _{i=1}^{\infty} A_i \right) \leq \sum_{i=1}^{\infty} \Pr(A_i).\]For two events, this is a straightforward consequence of the fact that
\[\Pr(A \cup B) = \Pr(A) + \Pr(B) - \Pr(A \cap B)\]and probabilities can never be negative. The same argument can be applied via induction to prove the inequality for all \(n\).
By applying DeMorgan’s laws, we can obtain the following corollary to the union bound, now applied to intersections:
Corollary: For a finite set of events \(A_1, A_2, \ldots, A_n\),
\[\Pr \left(\bigcap _{i=1}^n A_i \right) \ge \sum_{i=1}^n \Pr(A_i) - n + 1.\]