Union Bounds & Concentration — Union bounds and basic...

SECTION 1

Historical Context & Motivation

Probability theory has long grappled with a deceptively simple question: given a collection of events, how likely is it that at least one of them occurs? The union bound (also called Boole's inequality) provides the most elementary answer: simply sum the individual probabilities. While this bound is often loose, its simplicity and generality make it one of the most frequently invoked tools across combinatorics, statistical learning theory, and high-dimensional statistics. Alongside the union bound, the notion of concentration of measure — the phenomenon that well-behaved random variables rarely stray far from their expected values — forms the conceptual backbone of modern probabilistic analysis.

Understanding these two ideas together is essential because many proofs in probability and statistics follow a common template: first show that a single 'bad event' has small probability, then apply a union bound over all possible bad events, and finally appeal to a concentration inequality to control the probability of each individual bad event. This section traces the key milestones that led to our current understanding.

1854

Boole's Inequality

George Boole formalized the union bound in An Investigation of the Laws of Thought, establishing that P(A₁ ∪ ⋯ ∪ Aₙ) ≤ ∑ P(Aᵢ). This elementary yet powerful inequality became a cornerstone of combinatorial probability.

1867

Chebyshev's Inequality

Pafnuty Chebyshev proved that any random variable with finite variance concentrates around its mean: the probability of deviating by more than k standard deviations is at most 1/k². This gave the first general concentration result requiring no distributional assumptions beyond finite second moments.

1933

Kolmogorov's Axioms

Andrey Kolmogorov placed probability on rigorous measure-theoretic foundations. The subadditivity axiom (σ-subadditivity of measures) directly implies the countable union bound, situating Boole's inequality as a structural property of probability measures.

1963

Hoeffding's Inequality

Wassily Hoeffding published exponential concentration bounds for sums of bounded independent random variables, ushering in the era of sharp, sub-Gaussian tail control that dramatically improved upon Chebyshev-type bounds in many applications.

1990s–present

Concentration in High Dimensions

Researchers such as Michel Talagrand and Michel Ledoux developed powerful concentration inequalities (e.g., bounded differences, isoperimetric methods) that became indispensable in statistical learning theory, random matrix theory, and compressed sensing — settings where union bounds over exponentially many events are routine.

The central question this lesson addresses is: How do we control the probability that something goes wrong across many simultaneous events, and why do averages of random quantities tend to be predictable? The union bound and basic concentration inequalities provide the first-line answers, and mastering them unlocks the reasoning patterns used throughout advanced probability and statistics.

SECTION 2

Core Principles & Definitions

Before diving into calculations, it helps to lay out the foundational ideas that underpin both union bounds and concentration phenomena. These principles are surprisingly intuitive, yet they carry enormous power when wielded carefully in proofs and applications.

Subadditivity of Probability

For any countable collection of events A₁, A₂, …, the probability of their union is at most the sum of their individual probabilities. This follows directly from the σ-subadditivity of probability measures: P(⋃ Aᵢ) ≤ ∑ P(Aᵢ). No assumptions about dependence are required.

Worst-Case Summation

The union bound is tight when events are mutually exclusive and becomes increasingly loose when events overlap significantly. Recognizing when events have substantial overlap is critical for deciding whether a union bound suffices or a more refined technique (inclusion–exclusion, Lovász Local Lemma) is needed.

Concentration of Measure

A random variable X with expectation μ is said to concentrate if P(|X − μ| ≥ t) decreases rapidly as t grows. The speed of this decay — polynomial (Markov, Chebyshev), exponential (Hoeffding, Chernoff), or even Gaussian — characterizes how 'well-behaved' X is.

Tail Bound Hierarchy

Concentration inequalities form a hierarchy of increasing power and increasing assumptions. Markov's inequality requires only nonnegativity, Chebyshev requires finite variance, and Hoeffding/Chernoff require independence and boundedness or moment-generating function conditions.

Union Bound + Concentration = ε-net Arguments

A ubiquitous proof strategy is: (1) discretize a continuous parameter space into a finite ε-net of N points, (2) apply a concentration inequality at each point, and (3) union-bound over all N points. This template pervades empirical process theory, random matrix theory, and high-dimensional statistics.

✦ KEY TAKEAWAY

Think of the union bound like a fire-safety budget. If you have 100 rooms in a building and each room has at most a 0.1% chance of catching fire on any given day, then the probability of at least one fire is at most 100 × 0.1% = 10%. You've simply added up the worst-case scenarios — an overestimate, since two rooms rarely burn simultaneously, but it gives you a concrete safety guarantee. Concentration inequalities are what let you bound that 0.1% per-room probability in the first place, by showing that random deviations from the norm are inherently rare.

SECTION 3

Visual Explanation — The Union Bound in Action

The union bound becomes most transparent when visualized through Venn-style diagrams. The key geometric insight is that summing individual probabilities overcounts the intersection regions. The following diagram illustrates three events A₁, A₂, and A₃ within a sample space Ω, highlighting how the union bound relates to the true probability of the union.

Three events A₁, A₂, A₃ with individual probabilities 0.30, 0.25, 0.20. The union bound yields P(A₁ ∪ A₂ ∪ A₃) ≤ 0.75. The shaded overlap regions show where the bound overcounts. The exact probability via inclusion–exclusion would subtract pairwise intersections and add back the triple intersection.

In the diagram above, notice that the intersection regions (A₁∩A₂, A₁∩A₃, A₂∩A₃, and A₁∩A₂∩A₃) are counted multiple times when we naïvely sum P(A₁) + P(A₂) + P(A₃). The inclusion–exclusion principle corrects for this overcounting by alternately subtracting and adding intersection terms, but doing so requires knowledge of all pairwise and higher-order intersection probabilities — information that is often unavailable or computationally expensive. The beauty of the union bound is that it sidesteps this entirely, accepting a looser guarantee in exchange for needing zero information about dependence structure.

SECTION 4

Mathematical Framework

We now formalize the union bound and the three foundational concentration inequalities that typically accompany it in introductory treatments. Each result is stated precisely, and the key proof technique is sketched to build intuition for when and why each bound is useful.

The Union Bound (Boole's Inequality)

UNION BOUND

P(A₁ ∪ A₂ ∪ ⋯ ∪ Aₙ) ≤ ∑ᵢ₌₁ⁿ P(Aᵢ)

A₁, …, Aₙ are any events (not necessarily independent or disjoint) in a probability space (Ω, ℱ, P). The bound extends to countably many events by σ-subadditivity.

The proof is immediate from monotonicity and finite additivity. Write A₁ ∪ ⋯ ∪ Aₙ = ⋃ Bᵢ where B₁ = A₁ and Bᵢ = Aᵢ \ (A₁ ∪ ⋯ ∪ Aᵢ₋₁). The Bᵢ are disjoint, so P(⋃ Aᵢ) = ∑ P(Bᵢ) ≤ ∑ P(Aᵢ) since Bᵢ ⊆ Aᵢ.

Markov's Inequality

MARKOV'S INEQUALITY

P(X ≥ a) ≤ E[X] / a, for X ≥ 0, a > 0

X is a nonnegative random variable with finite expectation. This is the weakest but most general concentration bound — it requires only nonnegativity.

Chebyshev's Inequality

CHEBYSHEV'S INEQUALITY

P(|X − μ| ≥ t) ≤ σ² / t²

μ = E[X], σ² = Var(X). Obtained by applying Markov's inequality to the nonneg. variable (X − μ)². The decay is polynomial: O(1/t²).

Hoeffding's Inequality

HOEFFDING'S INEQUALITY

P(S̄ₙ − μ ≥ t) ≤ exp(−2n²t² / ∑(bᵢ − aᵢ)²)

S̄ₙ = (1/n) ∑ Xᵢ where X₁, …, Xₙ are independent with Xᵢ ∈ [aᵢ, bᵢ] a.s. and μ = E[S̄ₙ]. Here ∑(bᵢ − aᵢ)² is the sum over all n terms. For i.i.d. variables each in [0, 1] this sum equals n, so the exponent simplifies to −2nt². The tail decays exponentially (sub-Gaussian), offering a dramatic improvement over Chebyshev for bounded independent variables.

🔑 Proof Technique: The Chernoff Method

Hoeffding's inequality (and more generally, Chernoff bounds) are derived via the exponential moment method: for any s > 0, P(X ≥ a) = P(e^{sX} ≥ e^{sa}) ≤ E[e^{sX}] / e^{sa} by Markov's inequality applied to e^{sX}. One then optimizes over s to obtain the tightest bound. This elegant trick — converting a tail probability into a moment-generating function problem — is the engine behind all exponential concentration inequalities.

SECTION 5

Comparing Tail Decay — Polynomial vs. Exponential

One of the most important practical distinctions in concentration theory is the rate at which tail probabilities decay. This distinction directly determines how many events you can union-bound over before the total error probability becomes unacceptably large. If each individual event has probability ε, and there are N events, the union bound gives total error at most Nε. For this to remain small, you need ε ≤ δ/N for a target failure probability δ — meaning the per-event tail bound must shrink at least as fast as 1/N. Polynomial tail decay (Chebyshev) struggles when N is large, whereas exponential decay (Hoeffding) handles even exponentially large N gracefully.

Comparison of tail decay rates for three concentration inequalities. The Markov bound (yellow) decays as 1/t, Chebyshev (violet) decays as 1/t², and Hoeffding (green) decays exponentially in t². At moderate to large deviations, the exponential bound is dramatically tighter.

Practical capacity of each tail bound to sustain union bounds over N events. Hoeffding entries assume i.i.d. variables bounded in an interval of width 1 (e.g., [0,1]), giving ∑(bᵢ−aᵢ)² = n and the simplified two-sided form 2 exp(−2nt²).

Inequality	Assumptions	Tail Decay	Max N for Union Bound (δ = 0.05, t = 3σ)
Markov	X ≥ 0, finite E[X]	O(1/t)	Not directly applicable: Markov bounds P(X ≥ a) via E[X]/a and does not use σ, so '3σ' is not a natural parameterization. With only mean information, the per-event bound is not controlled by σ alone.
Chebyshev	Finite variance	O(1/t²)	At t = 3σ: per-event bound = 1/9 ≈ 0.111. Union bound ≤ 0.05 requires N × 0.111 ≤ 0.05, so N ≤ 0.45 — less than 1 event. Chebyshev cannot sustain even a single union-bounded event at this threshold.
Hoeffding	Independent, bounded	exp(−2nt²)	Per-event bound = 2 exp(−2nt²). Union bound ≤ 0.05 requires N ≤ 0.025 exp(2nt²), which grows exponentially in n — can handle N exponential in n.

The table makes the practical implications vivid. With Chebyshev's inequality at t = 3σ, each event has probability at most 1/9 ≈ 0.111, so a union bound over even a single event already exceeds a 5% target (since 0.111 > 0.05). With Hoeffding's bound, the per-event probability decays as 2 exp(−2nt²), which can be made tiny enough to union-bound over an exponentially growing collection — the regime relevant to learning theory and high-dimensional inference.

SECTION 6

Worked Example — Bounding Deviation of a Sample Mean

Consider the following scenario: a data scientist collects n = 200 independent observations X₁, …, X₂₀₀, each drawn uniformly from [0, 1], and computes the sample mean X̄ = (1/200) ∑ Xᵢ. She needs the probability that X̄ deviates from its expectation μ = 0.5 by more than 0.05. She also needs to ensure that, across K = 50 parallel experiments (different datasets), none of the sample means deviates by more than 0.05 from 0.5. We solve both parts.

Union Bound + Hoeffding for Parallel Experiments

Step 1 — Identify ParametersEach Xᵢ ∈ [aᵢ, bᵢ] = [0, 1], so bᵢ − aᵢ = 1 for all i. We have n = 200, μ = E[X̄] = 0.5, and deviation threshold t = 0.05. There are K = 50 parallel experiments. Target overall failure probability: δ = 0.05.

n = 200, t = 0.05, K = 50, δ = 0.05

Step 2 — Apply Hoeffding's Inequality to One ExperimentHoeffding's inequality (two-sided form) states P(|X̄ − μ| ≥ t) ≤ 2 exp(−2n²t² / ∑(bᵢ − aᵢ)²). Since each (bᵢ − aᵢ)² = 1 and there are n = 200 terms, ∑(bᵢ − aᵢ)² = 200. Substituting all values: 2 exp(−2 × 200² × 0.05² / 200) = 2 exp(−2 × 40000 × 0.0025 / 200) = 2 exp(−200 / 200) = 2 exp(−1.0) ≈ 2 × 0.3679 = 0.7358. Equivalently, since ∑(bᵢ − aᵢ)² = n for i.i.d. [0,1] variables, the exponent simplifies to −2n²t²/n = −2nt², confirming the result: 2 exp(−2 × 200 × 0.0025) = 2 exp(−1.0) ≈ 0.7358.

P(|X̄ − 0.5| ≥ 0.05) ≤ 2e⁻¹ ≈ 0.7358

Step 3 — Assess the Bound and Choose an Illustrative ThresholdThe per-experiment bound of ≈ 0.7358 is not useful for a union bound over K = 50 experiments, as 50 × 0.7358 far exceeds 1. To obtain a meaningful guarantee, we increase the deviation threshold to t = 0.1, which better illustrates how union bounds and concentration work together. With t = 0.1: 2 exp(−2 × 200 × 0.1²) = 2 exp(−2 × 200 × 0.01) = 2 exp(−4) ≈ 2 × 0.01832 = 0.0366 per experiment.

With t = 0.1: P(|X̄ − 0.5| ≥ 0.1) ≤ 2e⁻⁴ ≈ 0.0366 per experiment

Step 4 — Apply the Union Bound over K = 50 ExperimentsLet Eⱼ = {|X̄ⱼ − 0.5| ≥ 0.1} denote the 'bad event' for experiment j, for j = 1, …, 50. We want P(E₁ ∪ ⋯ ∪ E₅₀). By the union bound: P(⋃ⱼ₌₁⁵⁰ Eⱼ) ≤ ∑ⱼ₌₁⁵⁰ P(Eⱼ) ≤ 50 × 0.0366 = 1.83. Since 1.83 > 1, the bound is vacuous — it does not provide useful information. This illustrates that even exponential tail bounds can be overwhelmed if K is too large relative to the tail probability.

P(⋃ⱼ Eⱼ) ≤ 50 × 0.0366 = 1.83 (vacuous — exceeds 1)

Step 5 — Determine Required n for δ = 0.05We need 50 × 2 exp(−2n × 0.01) ≤ 0.05, i.e., exp(−0.02n) ≤ 0.0005, so 0.02n ≥ ln(2000) = 7.601, giving n ≥ 380.05. Thus n = 381 observations per experiment suffice. Verification: 100 × exp(−0.02 × 381) = 100 × exp(−7.62) ≈ 100 × 0.000489 = 0.0489 < 0.05. ✓

n ≥ 381 per experiment guarantees P(any deviation ≥ 0.1) ≤ 0.05 across all 50 experiments.

📐 PRACTICAL INSIGHT

The worked example reveals a crucial insight: the sample size n needed to ensure uniform control over K parallel events grows only as O(log K) thanks to the exponential decay of Hoeffding's bound. Doubling the number of experiments from 50 to 100 increases the required n by only about ln(2)/0.02 ≈ 35 additional samples — a remarkably mild cost. This logarithmic dependence on the number of events is why exponential concentration is so valuable in high-dimensional problems.

SECTION 7

Strengths, Limitations, and When to Go Beyond

The union bound combined with standard concentration inequalities is an extraordinarily versatile tool, but it is not always the best tool. Understanding when it works well and when it fails is an essential part of mathematical maturity in probability.

Strengths and limitations of the union bound approach

Aspect	Strengths	Limitations
Generality	No assumptions on dependence needed; applies to any events whatsoever.	Ignores structure — highly correlated events yield very loose bounds.
Simplicity	One-line proof; easy to apply in complex proofs without heavy machinery.	May be vacuous (exceed 1) when the number of events is large relative to per-event probabilities.
Composability	Seamlessly combines with any tail bound (Markov, Chebyshev, Hoeffding, Chernoff, etc.).	For continuous parameter spaces, discretization (ε-net) introduces additional approximation error.
Scalability	With exponential tail bounds, handles polynomially or even exponentially many events via log-factor costs.	With polynomial tail bounds (Chebyshev), fails for more than a handful of events.
Tightness	Tight when events are disjoint or nearly disjoint.	Can be off by orders of magnitude when events overlap heavily; inclusion–exclusion or Lovász Local Lemma may be needed.

⚠️ WHEN TO LOOK BEYOND

If the union bound is vacuous (total exceeds 1), consider: (1) the Lovász Local Lemma when events are mostly independent with limited local dependence; (2) second-moment methods (Paley–Zygmund, Cauchy–Schwarz) when you want lower bounds on P(X > 0); or (3) chaining and generic chaining for suprema of stochastic processes over rich index sets where naïve ε-net arguments are too wasteful.

SECTION 8

Connection to Advanced Concentration Theory

The union bound and basic concentration inequalities introduced in this lesson are the ground floor of a towering edifice. As problems grow in dimension and complexity — from finite unions to suprema over function classes, from independent to dependent data — more sophisticated tools become necessary. Yet every advanced method can be traced back to the simple ideas presented here.

From basic to advanced: the lineage of concentration tools.

Basic Tool (This Lesson)	Advanced Generalization	Key Improvement
Union bound over finite N events	Chaining / Dudley's entropy integral	Replaces log N with an integral over metric entropy, yielding tight bounds for Gaussian processes.
Hoeffding for bounded independent variables	Sub-Gaussian / sub-exponential theory	Extends to unbounded variables whose tails are controlled by moment-generating function conditions.
Chebyshev (variance-based)	Matrix concentration (Matrix Bernstein)	Extends scalar concentration to operator-norm bounds for sums of random matrices.
Union bound + per-event tail bound	Uniform convergence / VC theory	Controls supremum of empirical process over infinite function classes using combinatorial dimension.

As you advance through probability theory, statistical learning, and high-dimensional statistics, you will encounter these extensions repeatedly. The intuition you build now — that union bounds trade generality for looseness and that exponential tails are necessary for high-dimensional control — will serve as a reliable compass for navigating more complex arguments.

SECTION 9

Practice Problems

PROBLEM 1 — CONCEPTUAL

Explain why the union bound P(A₁ ∪ ⋯ ∪ Aₙ) ≤ ∑ P(Aᵢ) is always valid regardless of the dependence structure among the events. Under what condition is it tight (i.e., holds with equality)?

PROBLEM 2 — BASIC CALCULATION

Let X be a nonneg. random variable with E[X] = 4. Use Markov's inequality to bound P(X ≥ 20). Then suppose Var(X) = 9 and use Chebyshev's inequality to bound P(|X − 4| ≥ 6). Compare the two results.

PROBLEM 3 — INTERMEDIATE

Suppose you roll a fair die n = 600 times and let X̄ be the sample mean of the outcomes. Each outcome Xᵢ ∈ [1, 6]. Using Hoeffding's inequality, bound P(|X̄ − 3.5| ≥ 0.5). Then determine whether a union bound over K = 10 independent repetitions of this experiment keeps the total failure probability below 0.01.

PROBLEM 4 — APPLIED

A machine learning engineer trains a classifier and wants to guarantee that its test error is within ε = 0.03 of its training error simultaneously for each of d = 500 candidate feature subsets. Each feature subset yields an average over n i.i.d. bounded loss values in [0, 1]. Using Hoeffding + union bound, find the minimum sample size n needed so that the probability of any subset's gap exceeding ε is at most δ = 0.05.

PROBLEM 5 — CRITICAL THINKING

Consider events A₁, …, Aₙ where P(Aᵢ) = p for all i and n × p = c for a constant c > 0 (so p = c/n). (a) What does the union bound give for P(⋃ Aᵢ)? (b) If the events are independent, compute the exact probability of the union and compare it to the union bound as n → ∞. (c) Discuss the implications: when is the union bound a good approximation and when does it waste substantial probability?

SUMMARY

Lesson Summary

The union bound (Boole's inequality) states that P(A₁ ∪ ⋯ ∪ Aₙ) ≤ ∑ P(Aᵢ), providing a universal, dependence-free upper bound on the probability that at least one event in a collection occurs. It is tight for disjoint events and increasingly loose when events overlap. The bound's utility depends critically on how small the per-event probabilities P(Aᵢ) are, which is where concentration inequalities enter the picture. Markov's inequality (polynomial, O(1/t)) requires only nonnegativity, Chebyshev's inequality (polynomial, O(1/t²)) requires finite variance, and Hoeffding's inequality (exponential, e⁻ᶜᵗ²) requires independence and boundedness.

The canonical proof strategy in high-dimensional probability is to combine a per-event concentration bound with a union bound over all events. Because exponential tail bounds make each P(Aᵢ) decay as e⁻ᶜⁿ, the total error grows only as N × e⁻ᶜⁿ, remaining small even when N is polynomial or exponential in the problem dimension — a phenomenon that underpins ε-net arguments, VC theory, and uniform convergence throughout statistical learning and random matrix theory.