1.9 Union Bound

Union Bound

For any events $A_1,\dots ,A_N\subseteq \Omega$ in the same probability space, the union bound states that the probability of the union of the events is at most the sum of their individual probabilities. Formally,
$\mathbb{P}\left[{\bigcup }_{i=1}^N{A}_i\right]\le {\sum }_{i=1}^N\mathbb{P}[A_i].$

Intuition

Let’s consider why the union bound is true:

1. In the case of mutually exclusive events, their union is exactly equal to the sum of their marginal probabilities.
2. In the case of all other events, per the inclusion-exclusion principle, their union is less than their marginal probabilities.

There are no scenarios where the probability of the union exceeds the sum of the individual probabilities. This would imply the inclusion of probability mass outside the defined events, which violates the basic principles of both the union operation and probability as a whole. If you are still unsure, draw a Venn diagram and think about it!

Examples

Matching Beads

Sinho has a set of 2n beads (n ≥2) of n different colors, such that there are two beads of each color.

He wants to give out pairs of beads as gifts to all the other n−1 TAs, and plans on keeping the final

pair for himself (since he is, after all, also a TA). To do so, he first chooses two beads at random to

give to the first TA he sees. Then he chooses two beads at random from those remaining to give to

the second TA he sees. He continues giving each TA he sees two beads chosen at random from his

remaining beads until he has seen all n−1 TAs, leaving him with just the two beads he plans to

keep for himself. Prove that the probability that at least one of the other TAs (not including Sinho

himself) gets two beads of the same color is at most 1