the union bound (Boole's inequality)

If you worry about several bad things possibly happening, a crude but extremely useful estimate is: the chance that at least one of them happens is no more than the sum of their individual chances. If three components each fail with probability 1 percent, the chance that something fails is at most 3 percent. That simple add-up-the-risks rule is the union bound, also called Boole's inequality.

Precisely: for any events A_1, A_2, ..., A_n (no independence needed, no disjointness needed), P(A_1 or A_2 or ... or A_n) <= P(A_1) + P(A_2) + ... + P(A_n). Why an inequality and not equality? Because if some bad events overlap, adding their probabilities double-counts the overlap regions, so the true probability of the union is only smaller. Equality holds exactly when the events are mutually exclusive (no overlaps to double-count). It follows directly from the inclusion-exclusion principle by keeping only the first, positive layer and dropping all the correction terms.

Despite its crudeness, the union bound is one of the most powerful tools in probabilistic arguments. The classic move: to show none of n rare bad events happens, bound each one's probability by delta/n; then the union bound caps the total failure probability at n times delta/n = delta. This is how you turn a guarantee for one item into a guarantee for many simultaneously — the foundation of generalization bounds over large hypothesis classes, multiple-testing corrections, and high-probability statements about whole algorithms. The cost: when there are many highly correlated events, summing their probabilities can vastly overcount, making the bound very loose.