The Union Bound and Finite Hypothesis Classes

If you flip 20 fair coins 100 times each, purely by chance, one of those coins will probably come up heads far more than 50% of the time — not because that coin is special, but because you gave randomness 20 separate chances to fool you. The same thing happens when you evaluate many candidate models on the same test set: even if none of them are actually good, one of them will likely look good just from sampling luck, and the more models you try, the more likely that is. The union bound is the piece of probability that turns "the more you try, the more likely you get fooled" into an exact number.

The analogy: many lottery tickets, one lucky draw

If you buy one lottery ticket, your odds of winning are whatever they are. If you buy a thousand tickets, each with the same tiny odds, your overall odds of at least one winning ticket are much higher — not because any individual ticket got better, but because you gave luck a thousand chances to hand you a win. Evaluating a thousand candidate models against a test set is buying a thousand tickets in the "does this model look deceptively good by chance" lottery; the union bound tells you the price of playing that many times.

The formal statement

For any collection of "bad events" $B_1, \dots, B_H$ — one per hypothesis in a finite hypothesis class of size $H$, where $B_h$ is "hypothesis $h$'s training error is misleadingly far from its true error" — the union bound says:

$$P(B_1 \cup B_2 \cup \dots \cup B_H) \le \sum_{h=1}^{H} P(B_h)$$

In words: the probability that at least one of the $H$ hypotheses gets unlucky is at most the sum of each individual hypothesis's chance of getting unlucky — you simply add up the risks, even though the events can overlap, which always gives a valid (if sometimes loose) upper bound. Applied to learning: if each single hypothesis has at most $\delta$ chance of a misleadingly good training score (by a concentration bound like Hoeffding's), then across $H$ hypotheses, the chance that any one of them looks misleadingly good is at most $H\delta$ — grows linearly with how many models you tried.

Worked example 1: the raw arithmetic

Suppose each of 50 candidate trading signals independently has a 2% chance of showing spuriously good backtest performance purely from noise (a bad event with $P(B_h) = 0.02$). The union bound says the chance that at least one of the 50 looks spuriously good is at most $50 \times 0.02 = 1.0$, i.e., essentially guaranteed. Even at a stricter per-signal chance of $0.2\%$, testing 50 signals gives a bound of $50 \times 0.002 = 0.10$ — a 10% chance that some signal looks great purely by luck, even though every individual signal was individually quite reliable.

Worked example 2: solving for a safe sample size

To keep the overall failure probability at $\delta = 0.05$ while testing $H = 1{,}000$ hypotheses, each individual hypothesis needs its own failure probability capped at $\delta/H = 0.05/1000 = 0.00005$. Via Hoeffding's inequality, achieving that per-hypothesis bound with error tolerance $\epsilon = 0.02$ requires roughly $n \ge \frac{1}{2\epsilon^2}\ln(2H/\delta) = \frac{1}{2(0.0004)}\ln(40{,}000) \approx 1250 \times 10.6 \approx 13{,}300$ test examples. Testing 1,000 hypotheses safely needs meaningfully more held-out data than testing one — the union bound is exactly the term ($\ln H$) that grows the required sample size as the search gets wider.

Drag the curve above — the union bound's cost of searching more hypotheses grows only logarithmically ($\ln H$) inside the sample-size formula, which is why doubling your search space is far cheaper than doubling your error tolerance.

What this means in practice

Every time you backtest many strategy variants and pick the best-performing one, you are implicitly running a union bound over however many variants you tried — and the honest generalization guarantee for the winner is far weaker than the one-shot guarantee for a single pre-registered strategy. This is the formal backbone of why multiple-comparisons corrections (like Bonferroni, which is literally the union bound applied to hypothesis testing) exist, and why "we tested 500 signals and this one had a great Sharpe" should be read with deep skepticism absent a correction like this.