The union bound is ubiquitous in theoretical computer science, and perhaps in justification of this Andy Drucker mentioned in a lecture once a heuristic argument for its “tightness”. Just to write it out, the union bound takes

and approximates it as

Imagine if are “bad events” that occur with some tiny probability . The union bound says

If the events were fully independent, we would have the equality

Now when . So we have

This is equal to the bound spit out by the application of the union bound! In the case of fully independent events with small probabilities, we see the union bound is essentially tight. Full independence is rare, but in applications where low-probability events are slightly correlated, the union bound is also a good approximation.

### Like this:

Like Loading...

*Related*