Union Bounds for Maxima and Multiple Events

Why Bound the Chance of Any Failure?

Many probability questions concern a collection of possible failures: at least one estimate is inaccurate, at least one measurement is unusually large, or at least one of several conditions is violated. The event of interest is a union, and its probability can be controlled using only the probabilities of the individual events. Crucially, this control does not require the events to be independent.

The resulting inequality is simple, but its scope is broad. It converts separate probability bounds into a simultaneous guarantee, and it gives a direct tail bound for the maximum of finitely many random variables. It can also be conservative: if the events overlap substantially, adding their probabilities may count the same outcomes several times.

The Finite Union Bound

Theorem (Union Bound): Let $A_1,\ldots,A_m$ be events on the same probability space, where $m$ is a positive integer. Then $$ P\left(\bigcup_{i=1}^m A_i\right) \leq \sum_{i=1}^m P(A_i). $$ Since a probability cannot exceed 1, the sharper statement obtained by combining this with the trivial probability bound is $$ P\left(\bigcup_{i=1}^m A_i\right) \leq \min\left\{1,\sum_{i=1}^m P(A_i)\right\}. $$

No independence, mutual exclusivity, or common distribution is assumed. Each $A_i$ need only be an event, so the inequality applies to events with arbitrary dependence.

Proof: For an outcome $\omega$, let $\mathbf{1}_{A_i}(\omega)$ equal 1 when $\omega\in A_i$, and 0 otherwise. If $\omega$ belongs to at least one event, then the sum of the indicators is at least 1. If it belongs to none, the indicator of the union is 0. Thus, for every outcome, $$ \mathbf{1}_{\cup_{i=1}^m A_i} \leq \sum_{i=1}^m \mathbf{1}_{A_i}. $$ Taking expectations preserves the inequality. The expectation of an event's indicator is its probability, and expectation is additive for a finite sum. Therefore $$ P\left(\bigcup_{i=1}^m A_i\right) =E[\mathbf{1}_{\cup_{i=1}^m A_i}] \leq \sum_{i=1}^m E[\mathbf{1}_{A_i}] =\sum_{i=1}^m P(A_i). $$ Combining this with $P(\cup_i A_i)\leq 1$ gives the stated minimum bound. $\square$

Worked Example: Overlapping Events Need No Independence Assumption

Let $U$ be uniformly distributed on $[0,1]$, and define $A_1=\{U\leq 0.20\}$, $A_2=\{U\leq 0.35\}$, and $A_3=\{U\leq 0.10\}$. Find the union bound and the actual probability that at least one event occurs.

The individual probabilities are $$ P(A_1)=0.20,\qquad P(A_2)=0.35,\qquad P(A_3)=0.10. $$ Therefore the union bound is $$ P(A_1\cup A_2\cup A_3)\leq 0.20+0.35+0.10=0.65. $$

Here $A_1$ and $A_3$ are contained in $A_2$, so their union is exactly $A_2$. Consequently, $$ P(A_1\cup A_2\cup A_3)=P(A_2)=0.35. $$ The bound is valid but not tight: adding the separate probabilities counts outcomes in the overlap more than once. The calculation of the bound did not require us to model or estimate the dependence.

Applying the Bound to Maxima

For real-valued random variables $X_1,\ldots,X_m$, the event that their maximum exceeds a common threshold $t$ is exactly the event that at least one variable exceeds $t$. This equivalence turns the union bound into a tail bound for a maximum.

Corollary (Tail Bound for a Maximum): If $X_1,\ldots,X_m$ are real-valued random variables and $t\in\mathbb{R}$, then $$ P\left(\max_{1\leq i\leq m}X_i>t\right) \leq \sum_{i=1}^m P(X_i>t). $$ For absolute maxima, $$ P\left(\max_{1\leq i\leq m}|X_i|>t\right) \leq \sum_{i=1}^m P(|X_i|>t),\qquad t\geq 0. $$

Proof: For every outcome, $\max_{1\leq i\leq m}X_i>t$ holds if and only if $X_i>t$ for at least one index $i$. Hence $$ \left\{\max_{1\leq i\leq m}X_i>t\right\} =\bigcup_{i=1}^m\{X_i>t\}. $$ Applying the finite union bound gives the first inequality. Replacing each $X_i$ by $|X_i|$ gives the second; the condition $t\geq0$ is the usual range for an absolute-value threshold. $\square$

The same argument allows different thresholds. If $t_1,\ldots,t_m$ are real numbers, then $$ P\left(\text{there is an }i\text{ such that }X_i>t_i\right) \leq \sum_{i=1}^m P(X_i>t_i). $$ In this form, the bound can match the scale or tolerance relevant to each variable rather than imposing one common cutoff.

Worked Example: Bounding a Maximum from Marginal Tails

Suppose $X_1,X_2,X_3$ have the following marginal distributions, with no assumption about their joint distribution: $X_1=3$ with probability $0.04$ and $0$ otherwise; $X_2=5$ with probability $0.03$ and $0$ otherwise; and $X_3=-2$ with probability $0.05$ and $0$ otherwise. Bound the probability that $\max_i|X_i|>1$.

Because the nonzero value of each variable has absolute value greater than 1, $$ P(|X_1|>1)=0.04,\qquad P(|X_2|>1)=0.03,\qquad P(|X_3|>1)=0.05. $$ The event that the maximum exceeds 1 is the union of these three exceedance events. Thus $$ P\left(\max_{1\leq i\leq 3}|X_i|>1\right) \leq 0.04+0.03+0.05=0.12. $$ The conclusion is valid for any dependence structure consistent with the stated marginal probabilities. The bound does not claim the probability equals $0.12$; overlap among the exceedance events could make it smaller.

Allocating a Total Error Budget

A common use of the union bound is to ensure that several requirements hold simultaneously. If the probability of violating requirement $i$ is at most $\delta_i$, then the probability of any violation is at most the sum of those allowances. Choosing the allowances so that their sum is small gives a guarantee for all requirements together.

Simultaneous-Control Principle: Suppose $A_1,\ldots,A_m$ are failure events and $P(A_i)\leq\delta_i$ for each $i$, where each $\delta_i\geq0$. Then $$ P(\text{at least one failure})= P\left(\bigcup_{i=1}^m A_i\right) \leq \sum_{i=1}^m\delta_i. $$ In particular, if $\sum_i\delta_i\leq\delta$, then the probability that all requirements are met is at least $1-\delta$.

This result is sometimes called the Bonferroni inequality or the Bonferroni bound in its multiple-testing use. The conclusion concerns the probability of one or more errors, not the expected number of errors. It remains valid whether the individual events are independent, positively associated, or negatively associated.

Worked Example: Controlling Multiple False Rejections

Suppose a study tests 12 null hypotheses. Under the relevant null hypothesis for each test, assume the probability of a false rejection is at most $0.01$. Bound the probability of at least one false rejection, without assuming anything about dependence among the tests.

Let $A_i$ denote the event that test $i$ falsely rejects its null hypothesis. For each $i$, $P(A_i)\leq0.01$. Therefore $$ P(\text{at least one false rejection}) =P\left(\bigcup_{i=1}^{12}A_i\right) \leq \sum_{i=1}^{12}P(A_i) \leq 12(0.01)=0.12. $$ Thus the probability of no false rejections is at least $1-0.12=0.88$. This is a dependence-robust upper bound; the actual probability may be lower, but it cannot be inferred from the marginal bounds alone.

Unequal Thresholds and Simultaneous Accuracy

For a collection of estimates, the undesirable event may be that at least one estimation error is larger than its own tolerance. Write $A_i=\{|\hat{\theta}_i-\theta_i|>t_i\}$, where $t_i>0$ is chosen for component $i$. Then $$ P\left(\text{some }|\hat{\theta}_i-\theta_i|>t_i\right) \leq \sum_{i=1}^m P(|\hat{\theta}_i-\theta_i|>t_i). $$ This provides a modular strategy: establish a suitable probability bound for each component, then add the bounds. The componentwise bounds may come from different arguments, and the variables need not have identical distributions.

The error budget need not be divided equally. For example, if one component is especially important, it can be assigned a smaller failure allowance, provided the allowances for all components still sum to at most the desired overall level. Equal allocation is convenient, not required.

When the Bound Is Useful—and When It Is Loose

The union bound is most useful when separate tail probabilities are available but the joint distribution is unknown, complicated, or dependent. It is also useful when a guaranteed upper bound matters more than a sharp estimate. Its weakness is that it ignores overlap: if many events tend to occur together, their probabilities may add to a number far above the actual union probability.

The bound is exact when the events are pairwise disjoint, because no outcome is counted in more than one event. At the other extreme, if several events are identical, the sum can be many times larger than the probability of their union. For this reason, the bound can be improved by exploiting known structure, but such improvements require information beyond the separate event probabilities.

Common mistake: Treating the union bound as an equality, or multiplying complements as if the events were independent. In general, $P(\cup_i A_i)$ is not $\sum_iP(A_i)$, and $P(\cap_i A_i^c)$ is not necessarily $\prod_i(1-P(A_i))$. The correction is to use $P(\cup_i A_i)\leq\sum_iP(A_i)$ unless disjointness or independence has separately been established. Dependence does not invalidate the union bound; it only affects how sharp the bound is.

Check Your Understanding

Use the definitions and results above to answer these questions.

Three events have probabilities $0.12$, $0.08$, and $0.25$. What upper bound does the union bound give for the probability that at least one occurs?
Why does the maximum tail bound remain valid when the random variables are dependent?
If $P(A_i)\leq0.02$ for each of 15 events, what does the union bound say about the probability of at least one event occurring?
Give a dependence pattern under which the union bound is exact, and explain why.
Suppose $P(|X_1|>2)\leq0.04$ and $P(|X_2|>1)\leq0.03$. Give an upper bound for the probability that either variable exceeds its specified absolute threshold.