Overlap in the union bound 2026-10-14
For a finite family, the random variable counts the events that occur. Linearity of expectation gives , while is the exact union probability. Their difference isAn outcome in exactly events contributes extra counts, weighted by its probability. This nonnegative difference vanishes exactly in equality in Boole's inequality. For two events it is , as the inclusion-exclusion principle for probabilities shows. For more events, the Bonferroni inequalities use pairwise and higher intersection information to bound the exact union probability; blindly subtracting pairwise intersections from the sum gives a lower bound, rather than a corrected upper bound.
Severe overlap can make the union bound arbitrarily pessimistic. Let all events be the same event with probability , where is an integer. A concrete model is the discrete uniform distribution on with . The exact union probability is , whereas the sum and capped bound are both one. The ratio is : adding more names for the same event does not create more ways to fail. The identity above describes the gap in the uncapped sum; capping at one can reduce that gap.