# The union bound

## In words...

The union bound is a basic inequality in probability that states that the union of events cannot have a larger probability than the sum of the respective probabilities of the events.

## In pictures...

Here is an abstract view of two events ($A$ and $B$) and their union.

The probability of the union is
which is lower than
the probability of $A$ () plus the probability of $B$ ().

## In maths...

For two events $A$ and $B$, the union bound states that $$P(A\cup B) \leq P(A) + P(B) ,$$ and more generally that, for a countable set of events $\{A_i\}$, $$P\left(\bigcup_{i=1}^n A_i\right) \leq \sum_{i=1}^n P(A_i) .$$

The union bound for two events can be easily shown from the explicit formula of the probability of the union, $$P(A\cup B) = P(A) + P(B) - P(A \cap B) ,$$ and the fact that (or the axiom stating that) the probability of any event (and in particular $A\cap B$) is non-negative. The generalization to countable sets of events can be proved by induction with a similar reasoning (using $A = \cup_{i=1}^{n-1} A_i$ and $B=A_{n}$ ).