union bound

It's a basic law of probability that, given two events A and B, the probability that at least one of them occurs is given by

This counts the worlds in which $A$ happens and the worlds in which $B$ happens, then subtracts out the worlds which were double-counted.

Sometimes we don't know $P(A \cap B)$, i.e., we are not sure whether or how $A$ and $B$ co-occur. Since probabilities are nonnegative, we can just omit this term from the equation, turning the equality into an inequality. This is the union bound:

The bound is tight when $A$ and $B$ are disjoint events. It can of course be generalized to multiple events in the obvious way: