The Union Bound

Statement

Boole’s inequality (Union Bound): For any events $E_1, E_2, \ldots, E_n$:

$P\left(\bigcup_{i=1}^{n} E_i\right) \leq \sum_{i=1}^{n} P(E_i)$

The probability of at least one event occurring is at most the sum of their individual probabilities.

For infinitely many events:

$P\left(\bigcup_{i=1}^{\infty} E_i\right) \leq \sum_{i=1}^{\infty} P(E_i)$

Proof

By inclusion-exclusion:

$P(E_1 \cup E_2) = P(E_1) + P(E_2) - P(E_1 \cap E_2) \leq P(E_1) + P(E_2)$

since $P(E_1 \cap E_2) \geq 0$.

By induction: assume true for $n-1$ events. Then:

$P\left(\bigcup_{i=1}^{n} E_i\right) = P\left(\bigcup_{i=1}^{n-1} E_i\right) + P(E_n) - P\left(\bigcup_{i=1}^{n-1} E_i \cap E_n\right) \leq \sum_{i=1}^{n-1} P(E_i) + P(E_n) = \sum_{i=1}^{n} P(E_i)$

When is Equality Achieved?

Equality holds when all $E_i$ are mutually exclusive: when $E_i \cap E_j = \emptyset$ for all $i \neq j$, the intersection terms vanish and the bound becomes exact.

Why the Union Bound Matters

The union bound provides a simple upper bound when:

1. Exact probabilities are hard to compute
2. We need to prove something is “small enough”
3. Events may be dependent (union bound doesn’t require independence)

It is often used in algorithm analysis and error bounds.

Example: Hash Collisions

A hash table has $m$ buckets. We insert $n$ keys. Let $E_i$ be the event that key $i$ collides with some earlier key.

The probability of at least one collision satisfies:

$P(\text{some collision}) \leq \sum_{i=1}^{n} P(E_i)$

If each key lands uniformly: $P(E_i) \leq \frac{i-1}{m}$. Then:

$P(\text{some collision}) \leq \sum_{i=1}^{n} \frac{i-1}{m} = \frac{n(n-1)}{2m}$

This is the birthday problem bound.

Example: Error Bounds

A system makes $n$ independent trials, each with error probability $\epsilon$. Let $E_i$ = “error on trial $i$”.

$P(\text{at least one error}) \leq n \epsilon$

If $\epsilon = \frac{1}{n^2}$, then $P(\text{error}) \leq \frac{1}{n}$.

This is useful in probabilistic analysis: if each step has small error, the total error is bounded.

Frechet Inequalities

Related bounds for intersections:

$\max\{0, \sum_i P(E_i) - (n-1)\} \leq P\left(\bigcap_{i=1}^{n} E_i\right) \leq \min_i P(E_i)$

The upper bound follows from monotonicity: $\bigcap E_i \subseteq E_j$ for each $j$, so $P(\bigcap E_i) \leq P(E_j)$.

Bonferroni Correction

The union bound motivates multiple testing corrections. If we run $n$ hypothesis tests, each at significance level $\alpha$, the probability of at least one false positive is at most $n\alpha$.

To ensure overall error rate $\alpha$, use threshold $\alpha/n$ for each test.

Comparing with Exact Calculation

Scenario	Exact	Union Bound
Mutually exclusive	$\sum P(E_i)$	$\sum P(E_i)$ (tight)
Independent	$1 - \prod(1-P(E_i))$	$\sum P(E_i)$ (loose when $P(E_i)$ not tiny)
General case	Inclusion-exclusion	$\sum P(E_i)$

The union bound is loosest when probabilities are large and events overlap significantly.

Summary

• Union bound: $P(\bigcup E_i) \leq \sum P(E_i)$
• Equality when: events are mutually exclusive
• Useful for: simpler analysis, error bounds, algorithm correctness proofs
• Limitation: can be very loose for large probabilities and dependent events