Probability & The Union Bound

A probability space is a triple $(\Omega, \mathcal{F}, P)$ where:

• $\Omega$ is a non-empty set, the sample space — the set of all possible outcomes.
• $\mathcal{F}$ is a collection of subsets of $\Omega$, the events — sets to which we are willing to assign a probability. We require $\Omega \in \mathcal{F}$, $A^c \in \mathcal{F}$ whenever $A \in \mathcal{F}$, and $\bigcup_n A_n \in \mathcal{F}$ whenever each $A_n \in \mathcal{F}$ (closure under countable unions).
• $P \colon \mathcal{F} \to [0, 1]$ is a function satisfying three axioms:
  • (K1) Non-negativity. $P(A) \geq 0$ for every $A \in \mathcal{F}$.
  • (K2) Normalization. $P(\Omega) = 1$.
  • (K3) Countable additivity. For any disjoint sequence $(A_n)_{n \geq 1}$ of events, $P\!\left(\bigcup_n A_n\right) = \sum_n P(A_n)$.

The closure conditions on $\mathcal{F}$ make it a sigma-algebra. Why bother — why not let every subset be an event? For finite or countable $\Omega$, the answer is: we can let every subset be an event, by taking $\mathcal{F} = 2^\Omega$. The condition is automatically satisfied and the question never arises. For uncountable $\Omega$ — like $[0, 1]$ with the “length” probability — there exist subsets to which no consistent probability can be assigned, and $\mathcal{F}$ has to be smaller than $2^\Omega$. That non-trivial story is told in Sigma-Algebras & Measures (forward). For this topic, take $\mathcal{F}$ to be “the subsets we know how to measure” and proceed.

Let $(\Omega, \mathcal{F}, P)$ be a probability space. Then:

1. $P(\emptyset) = 0$.
2. $P(A^c) = 1 - P(A)$ for every $A \in \mathcal{F}$.
3. Monotonicity: if $A \subseteq B$, then $P(A) \leq P(B)$.
4. Finite additivity: for disjoint events $A_1, \ldots, A_n$, $P\!\left(\bigcup_{i=1}^n A_i\right) = \sum_{i=1}^n P(A_i)$.
5. Continuity from below: if $A_1 \subseteq A_2 \subseteq \cdots$ is an increasing sequence of events, then $P\!\left(\bigcup_n A_n\right) = \lim_{n \to \infty} P(A_n)$.

(1) Take $A_n = \emptyset$ for all $n$ in (K3). The events are disjoint, so $P(\emptyset) = P\!\left(\bigcup_n \emptyset\right) = \sum_n P(\emptyset)$. If $P(\emptyset) > 0$ then the right-hand side is $+\infty$, contradicting $P(\emptyset) \leq 1$. So $P(\emptyset) = 0$.

(2) $\Omega = A \sqcup A^c$ disjointly, so by (K3) applied to the finite sequence $(A, A^c, \emptyset, \emptyset, \ldots)$ and (1), $1 = P(\Omega) = P(A) + P(A^c)$.

(3) Write $B = A \sqcup (B \setminus A)$ disjointly. By (K3) (or by (4) applied to a 2-element disjoint family), $P(B) = P(A) + P(B \setminus A) \geq P(A)$ since $P(B \setminus A) \geq 0$ by (K1).

(4) Pad the finite disjoint sequence with empty sets: $A_1, \ldots, A_n, \emptyset, \emptyset, \ldots$. Apply (K3) and use (1) to discard the empty-set terms.

(5) Set $B_1 = A_1$ and $B_k = A_k \setminus A_{k-1}$ for $k \geq 2$. The $(B_k)$ are pairwise disjoint, $\bigcup_n B_n = \bigcup_n A_n$ (since the chain is increasing), and $\bigcup_{k \leq n} B_k = A_n$ for every $n$. By (K3) and (4):

$P\!\left(\bigcup_n A_n\right) = P\!\left(\bigcup_n B_n\right) = \sum_{k=1}^\infty P(B_k) = \lim_{n \to \infty} \sum_{k=1}^n P(B_k) = \lim_{n \to \infty} P(A_n).$

The convergence of the limit on the right is automatic — partial sums of a non-negative series are monotone increasing and bounded by $1$, so they converge. $\blacksquare$

Let $\Omega = \{1, 2, 3, 4, 5, 6\}$, $\mathcal{F} = 2^\Omega$, $P(\{k\}) = 1/6$ for each $k$. By finite additivity, the probability of any event is the sum of the per-outcome probabilities of its members. For instance, $P(\text{even roll}) = P(\{2, 4, 6\}) = 3/6 = 1/2$, and $P(\text{roll is at most 4}) = P(\{1, 2, 3, 4\}) = 4/6 = 2/3$. The axioms reduce to “count and divide.”

Let $\Omega = \{1, 2, 3, \ldots\}$ and define $P(\{k\}) = 2^{-k}$. Since $\sum_{k=1}^\infty 2^{-k} = 1$, this defines a probability measure on $\Omega$ by countable additivity: $P(A) = \sum_{k \in A} 2^{-k}$ for every $A \subseteq \Omega$. This is the “geometric trials” model — the probability of needing exactly $k$ trials until the first success, when each trial is a fair coin. The sample space is countably infinite; the axioms still apply unchanged.

Let $\Omega = [0, 1]$ and define $P([a, b]) = b - a$ for $0 \leq a \leq b \leq 1$. This is the “uniform random number” model. To say which subsets of $[0, 1]$ are in $\mathcal{F}$ in full generality requires the measure-theoretic machinery of Sigma-Algebras & Measures (forward). For this topic, take $P([a, b]) = b - a$ on intervals as an oracle and proceed; no construction in the body of this topic depends on which specific subsets of $[0, 1]$ are measurable.

Why does (K3) ask for countable additivity rather than just finite additivity? Because the most important consequences — continuity from below (Proposition 1(v)), the first Borel–Cantelli lemma (Theorem 3), and the convergence of partial-sum probabilities — all require taking limits of an infinite sequence of disjoint events. A theory built on finite additivity alone cannot say “the probability that heads occurs infinitely often is zero” — that statement is about an infinite intersection of unions, and finite additivity gives no access to the limit. The price of countable additivity is the sigma-algebra constraint on $\mathcal{F}$; the reward is the entire analytic machinery of the rest of this topic.

For events $A, B \in \mathcal{F}$ with $P(B) > 0$, the conditional probability of $A$ given $B$ is

$P(A \mid B) = \frac{P(A \cap B)}{P(B)}.$

Conditioning on $B$ rescales the universe to the part of $\Omega$ where $B$ occurred. Three things follow immediately: (i) $P(\Omega \mid B) = P(B)/P(B) = 1$, so $P(\cdot \mid B)$ is normalized; (ii) $P(A \mid B) \geq 0$ for every $A$, so it is non-negative; (iii) countable additivity of $P(\cdot \mid B)$ follows from countable additivity of $P$ applied to the numerator. So $P(\cdot \mid B)$ is itself a probability measure on $(\Omega, \mathcal{F})$ — a fact we will use without further comment.

For events $A_1, A_2, \ldots, A_n$ with $P(A_1 \cap \cdots \cap A_{n-1}) > 0$,

$P(A_1 \cap A_2 \cap \cdots \cap A_n) = P(A_1) \cdot P(A_2 \mid A_1) \cdot P(A_3 \mid A_1 \cap A_2) \cdots P(A_n \mid A_1 \cap \cdots \cap A_{n-1}).$

If $(B_i)_{i \in I}$ is a finite or countable partition of $\Omega$ (the $B_i$ are pairwise disjoint and $\bigcup_i B_i = \Omega$) with each $P(B_i) > 0$, then for any event $A$:

$P(A) = \sum_i P(A \mid B_i) \, P(B_i).$

For events $A, B$ with $P(A), P(B) > 0$:

$P(A \mid B) = \frac{P(B \mid A) \, P(A)}{P(B)}.$

Combined with the law of total probability (when the denominator is unknown), for any partition $(A_j)$ with $P(A_j) > 0$:

$P(A_j \mid B) = \frac{P(B \mid A_j) \, P(A_j)}{\sum_i P(B \mid A_i) \, P(A_i)}.$

• Events $A$ and $B$ are independent if $P(A \cap B) = P(A) \, P(B)$.
• A family $(A_i)_{i \in I}$ is mutually independent (or simply independent) if for every finite subset $J \subseteq I$,

$P\!\left(\bigcap_{i \in J} A_i\right) = \prod_{i \in J} P(A_i).$

• A family is pairwise independent if every pair of events in the family is independent.

Take $\Omega = \{(0, 0, 0), (0, 1, 1), (1, 0, 1), (1, 1, 0)\}$ — four outcomes, each with probability $1/4$. Let $A_i$ be the event “the $i$-th coordinate equals $1$.” Then $P(A_i) = 1/2$ for each $i$ (two of the four outcomes have a $1$ in position $i$).

For any $i \neq j$, exactly one of the four outcomes has $1$s in both positions, so $P(A_i \cap A_j) = 1/4 = P(A_i) P(A_j)$. Every pair is independent.

But $A_1 \cap A_2 \cap A_3$ would require an outcome with $1$s in all three positions — and there is no such outcome in $\Omega$. So $P(A_1 \cap A_2 \cap A_3) = 0$, while $P(A_1) P(A_2) P(A_3) = 1/8$. The three events are pairwise independent but not mutually independent.

The structural reason: the third coordinate of each outcome equals the parity (XOR) of the first two. Knowing any one coordinate tells you nothing about another; knowing any two determines the third. Independence is a family-level property, not a sum of pairwise properties.

Two events $A$ and $B$ are independent under one probability measure $P$ and dependent under another, even when the underlying sets $A, B \subseteq \Omega$ are the same. Independence is a property of the triple $(A, B, P)$, not of the events alone. In statistical practice this means independence is an assumption that needs justification, not a logical certainty — two events about completely different physical systems can still be statistically dependent if the data-generating distribution links them.

For any countable sequence of events $(A_n)_{n \geq 1}$ in a probability space:

$P\!\left(\bigcup_n A_n\right) \leq \sum_n P(A_n).$

Equality holds if and only if the events are pairwise disjoint up to a null set — i.e., $P(A_i \cap A_j) = 0$ for every $i \neq j$.

Define a disjointified sequence: set $B_1 = A_1$, and for $n \geq 2$ let $B_n = A_n \setminus \bigcup_{k < n} A_k$. Three properties hold by construction.

First, the $(B_n)$ are pairwise disjoint: if $i < j$, then $B_j \subseteq A_j \setminus A_i$, so $B_j$ contains no point of $A_i \supseteq B_i$.

Second, $B_n \subseteq A_n$ for every $n$ (subtracting a set can only make $A_n$ smaller).

Third, $\bigcup_n B_n = \bigcup_n A_n$. The $\subseteq$ direction is immediate from $B_n \subseteq A_n$. For the $\supseteq$ direction: any $\omega \in \bigcup_n A_n$ lies in some $A_n$; let $n$ be the smallest index with $\omega \in A_n$. Then $\omega \in A_n$ but $\omega \notin A_k$ for $k < n$, so $\omega \in B_n$.

Now apply countable additivity to $(B_n)$ and monotonicity to $B_n \subseteq A_n$:

$P\!\left(\bigcup_n A_n\right) = P\!\left(\bigcup_n B_n\right) = \sum_n P(B_n) \leq \sum_n P(A_n).$

For the equality case: $P(B_n) = P(A_n \setminus \bigcup_{k < n} A_k) = P(A_n) - P(A_n \cap \bigcup_{k < n} A_k)$ by Proposition 1(iv) applied to the disjoint union $A_n = B_n \sqcup (A_n \cap \bigcup_{k < n} A_k)$. So $\sum_n P(B_n) = \sum_n P(A_n)$ forces every $P(A_n \cap \bigcup_{k < n} A_k) = 0$, which is equivalent to every pairwise intersection $P(A_i \cap A_j) = 0$ for $i \neq j$. $\blacksquare$

For any finite or countable family of events $A_1, A_2, \ldots$:

$P\!\left(\bigcap_i A_i\right) \geq 1 - \sum_i P(A_i^c).$

By De Morgan, $\left(\bigcap_i A_i\right)^c = \bigcup_i A_i^c$. So

$P\!\left(\bigcap_i A_i\right) = 1 - P\!\left(\bigcup_i A_i^c\right) \geq 1 - \sum_i P(A_i^c)$

where the inequality is Boole applied to the complements. $\blacksquare$

This is the canonical application of Corollary 1, and Puzzle 1 of §1 resolved. Suppose we run $m$ statistical tests; let $A_i^c$ be the event “test $i$ falsely rejects the null hypothesis.” If each test is run at level $\alpha_0$ — that is, $P(A_i^c) \leq \alpha_0$ under the null — then by Boole on the complements,

$P(\text{some test falsely rejects}) = P\!\left(\bigcup_i A_i^c\right) \leq \sum_i P(A_i^c) \leq m \alpha_0.$

Choosing $\alpha_0 = \alpha / m$ guarantees the family-wise error rate is at most $\alpha$, regardless of the dependence between the tests. The price is power: each individual test is run at a much stricter level than $\alpha$, so the test loses sensitivity. This is the trade-off every multiple-testing correction faces, and Bonferroni is the simplest possible solution. See Multiple Testing and False Discovery → formalStatistics for sharper procedures (Holm step-down, Hochberg, Benjamini–Hochberg FDR control) that all begin from this same union-bound observation.

This pattern will appear repeatedly. Let $X_1, \ldots, X_m$ be random variables — possibly dependent in complicated ways — and suppose each satisfies the same per-variable tail bound $P(|X_i| > t) \leq \delta(t)$. Then by Boole,

$P\!\left(\max_i |X_i| > t\right) = P\!\left(\bigcup_i \{|X_i| > t\}\right) \leq m \, \delta(t).$

To control the maximum at confidence $1 - \delta_0$, choose $t$ so that $m \, \delta(t) \leq \delta_0$ — equivalently, $\delta(t) \leq \delta_0 / m$. For the Hoeffding tail $\delta(t) = 2 e^{-2 n t^2}$ that we will prove in §8, this gives $t = \sqrt{\log(2 m / \delta_0) / (2 n)}$ — the classical $\sqrt{\log m}$ price of taking a union over $m$ events.

The pattern is so general that, in machine-learning practice, “apply a union bound” is almost always shorthand for this single move: per-event exponential tail, $m$ events, pay a $\sqrt{\log m}$ tax in the deviation.

Take $m = 10$ fair, independent coins; let $A_i$ be the event “coin $i$ lands heads.” The exact probability of at least one head is $1 - (1/2)^{10} = 1023 / 1024 \approx 0.999$. The union bound gives

$P\!\left(\bigcup_i A_i\right) \leq \sum_i P(A_i) = 10 \cdot \frac{1}{2} = 5,$

which is useless — it exceeds $1$, the absolute upper bound on any probability. The union bound is tight when events are nearly disjoint and uninformative when events are highly overlapping. Drag the circles in the flagship visualization together to see the bound’s ratio blow up; drag them apart to see the bound recover to exactness.

Loose bounds are not failures. They are advertisements for a different tool — usually inclusion–exclusion (§5) or a structural argument that exploits the overlap. The union bound’s value is not its sharpness but its generality: it asks nothing about how the events relate.

Three closely-related results live in this chapter. Boole’s inequality (Theorem 1) is a one-sided upper bound on $P(\bigcup A_i)$. Bonferroni’s inequality (Corollary 1) is the lower bound on $P(\bigcap A_i)$ that falls out of Boole on the complements. Inclusion–exclusion (Theorem 2 below) is an exact equality. The reason to reach for Boole instead of inclusion–exclusion in a proof is that Boole needs nothing about pairwise or higher-order intersections — only the marginal $P(A_i)$. This is exactly what makes Boole the workhorse of high-dimensional and distribution-free arguments: in those settings, joint probabilities of $m$ events are typically unknown or uncomputable, but marginals are not.

For any finite family of events $A_1, A_2, \ldots, A_n$:

$P\!\left(\bigcup_{i=1}^n A_i\right) = \sum_{k=1}^n (-1)^{k+1} \sum_{1 \leq i_1 < i_2 < \cdots < i_k \leq n} P(A_{i_1} \cap A_{i_2} \cap \cdots \cap A_{i_k}).$

Proof sketch by induction on $n$. The base case $n = 2$ is

$P(A \cup B) = P(A) + P(B) - P(A \cap B),$

which follows from $A \cup B = A \sqcup (B \setminus A)$ disjointly and $P(B) = P(A \cap B) + P(B \setminus A)$.

For the inductive step, suppose the formula holds for $n - 1$ events. Write

$\bigcup_{i=1}^n A_i = \left(\bigcup_{i=1}^{n-1} A_i\right) \cup A_n,$

apply the $n = 2$ case to the two events $\bigcup_{i \leq n-1} A_i$ and $A_n$:

$P\!\left(\bigcup_{i=1}^n A_i\right) = P\!\left(\bigcup_{i=1}^{n-1} A_i\right) + P(A_n) - P\!\left(\bigcup_{i=1}^{n-1} (A_i \cap A_n)\right).$

The induction hypothesis applies twice — to the first term (an $(n-1)$-fold union) and to the third term (the union of the $n-1$ intersections $A_i \cap A_n$, also an $(n-1)$-fold union of events). Expand both, collect terms by intersection cardinality, and verify that the signs and coefficients combine to give the claimed formula. The algebra is mechanical and is performed in full in the companion notebook. $\blacksquare$

For events $A, B, C$:

$P(A \cup B \cup C) = P(A) + P(B) + P(C) - P(A \cap B) - P(A \cap C) - P(B \cap C) + P(A \cap B \cap C).$

Verification on the uniform model over $\{0, 1\}^3$. Let $\Omega = \{0, 1\}^3$ with each outcome having probability $1/8$, and let $A_i$ be the event “the $i$-th coordinate is $1$.” Then $P(A_i) = 1/2$, $P(A_i \cap A_j) = 1/4$ for $i \neq j$, and $P(A_1 \cap A_2 \cap A_3) = 1/8$. The right-hand side is $3 \cdot 1/2 - 3 \cdot 1/4 + 1/8 = 12/8 - 6/8 + 1/8 = 7/8$, which matches $P(A_1 \cup A_2 \cup A_3) = 1 - P(\text{all zero}) = 1 - 1/8 = 7/8$. The accompanying notebook reproduces this and the 4-event and 5-event cases for sanity.

A derangement is a permutation with no fixed points. The probability that a uniformly random permutation $\pi$ of $\{1, 2, \ldots, n\}$ is a derangement equals

$\frac{D_n}{n!} = \sum_{k=0}^n \frac{(-1)^k}{k!} \;\xrightarrow{n \to \infty}\; \frac{1}{e} \approx 0.3679.$

The proof is inclusion–exclusion in three lines. Let $A_i = \{\pi(i) = i\}$ be the event ”$i$ is a fixed point.” Then $P(A_i) = (n-1)!/n! = 1/n$ — once $\pi(i) = i$ is fixed, the remaining $n - 1$ positions can be permuted in $(n-1)!$ ways. More generally, $P(A_{i_1} \cap \cdots \cap A_{i_k}) = (n-k)!/n!$ for any $k$ distinct indices, and there are $\binom{n}{k}$ such $k$-subsets. Inclusion–exclusion gives

$P\!\left(\bigcup_i A_i\right) = \sum_{k=1}^n (-1)^{k+1} \binom{n}{k} \frac{(n-k)!}{n!} = \sum_{k=1}^n \frac{(-1)^{k+1}}{k!}.$

Subtracting from $1$ gives the derangement probability $\sum_{k=0}^n (-1)^k / k!$, which is the partial-sum approximation to $e^{-1}$.

This is a classical combinatorial identity, but it is also a sanity check for the analytic side: by Series Convergence & Tests the alternating series $\sum (-1)^k / k!$ converges absolutely to $e^{-1}$, and the rate of convergence is faster than geometric — even at $n = 8$ the derangement probability is correct to four decimal places.

Boole’s inequality is the first member of a hierarchy. Truncating the inclusion–exclusion alternating sum at an even number of terms gives an upper bound on $P(\bigcup A_i)$; truncating at an odd number gives a lower bound. The first odd truncation — a single term, $\sum_i P(A_i)$ — is exactly Boole. The next two truncations are

$\sum_i P(A_i) - \sum_{i < j} P(A_i \cap A_j) \leq P\!\left(\bigcup_i A_i\right) \leq \sum_i P(A_i) - \sum_{i < j} P(A_i \cap A_j) + \sum_{i < j < k} P(A_i \cap A_j \cap A_k).$

(The lower bound is the “Bonferroni depth-2” bar in the flagship visualization.) The full hierarchy — Bonferroni’s inequalities — provides arbitrarily tight bounds at the cost of summing $\binom{m}{k}$ joint probabilities at depth $k$. In practice we rarely go past depth 2, because the gain in tightness beyond that is small relative to the explosion of joint terms.

For a sequence of events $(A_n)_{n \geq 1}$, the event ”$A_n$ occurs infinitely often” is

$\{A_n \text{ i.o.}\} := \limsup_n A_n = \bigcap_{N = 1}^\infty \bigcup_{n = N}^\infty A_n.$

Its complement is the event ”$A_n$ occurs only finitely many times”:

$\{A_n \text{ f.o.}\} = (\limsup_n A_n)^c = \liminf_n A_n^c = \bigcup_{N = 1}^\infty \bigcap_{n = N}^\infty A_n^c.$

The definition is the set-theoretic limsup the reader saw in Sequences, Limits & Convergence translated into events. A point $\omega \in \Omega$ is in $\limsup_n A_n$ precisely when $\omega$ belongs to infinitely many of the $A_n$. The “for every $N$ there exists $n \geq N$” structure of the definition is exactly the standard $\forall N \, \exists n \geq N$ unwinding of “infinitely often.”

The complementation rule $(\limsup A_n)^c = \liminf A_n^c$ — a countable De Morgan — is used in the proof of the second Borel–Cantelli lemma. Verify by chasing definitions:

$\left(\bigcap_N \bigcup_{n \geq N} A_n\right)^c = \bigcup_N \bigcap_{n \geq N} A_n^c.$

If $\sum_n P(A_n) < \infty$, then

$P(A_n \text{ i.o.}) = 0.$

By monotonicity of $P$ and Boole’s inequality, for every $N \geq 1$:

$P\!\left(\bigcup_{n \geq N} A_n\right) \leq \sum_{n \geq N} P(A_n).$

Since $\sum_n P(A_n) < \infty$, the tail of the series satisfies $\sum_{n \geq N} P(A_n) \to 0$ as $N \to \infty$ — this is the definition of convergence of a series of non-negative terms (see Series Convergence & Tests).

Now $\{A_n \text{ i.o.}\} = \bigcap_N \bigcup_{n \geq N} A_n$ is a decreasing intersection: as $N$ grows, fewer terms are in the union, so $\bigcup_{n \geq N} A_n$ shrinks. By continuity of probability (Proposition 1(v) applied to complements, or its mirror image for decreasing sequences):

$P(A_n \text{ i.o.}) = \lim_{N \to \infty} P\!\left(\bigcup_{n \geq N} A_n\right) \leq \lim_{N \to \infty} \sum_{n \geq N} P(A_n) = 0.$

Since probabilities are non-negative, $P(A_n \text{ i.o.}) = 0$. $\blacksquare$

If the events $(A_n)$ are mutually independent and $\sum_n P(A_n) = \infty$, then

$P(A_n \text{ i.o.}) = 1.$

It suffices to show that $P\!\left(\bigcap_{n \geq N} A_n^c\right) = 0$ for every $N$, because then by countable subadditivity (Boole) on the union $\bigcup_N \bigcap_{n \geq N} A_n^c$, the event $\{A_n \text{ f.o.}\}$ has probability $0$ and its complement $\{A_n \text{ i.o.}\}$ has probability $1$.

Fix $N$ and any finite truncation $M \geq N$. By mutual independence of the $A_n$‘s, the events $A_N^c, A_{N+1}^c, \ldots, A_M^c$ are also mutually independent (the complement of an independent event is independent of the original family). So

$P\!\left(\bigcap_{n = N}^M A_n^c\right) = \prod_{n = N}^M P(A_n^c) = \prod_{n = N}^M (1 - P(A_n)).$

Use the inequality $1 - x \leq e^{-x}$ for $x \in [0, 1]$ on each factor:

$\prod_{n = N}^M (1 - P(A_n)) \leq \prod_{n = N}^M e^{-P(A_n)} = \exp\!\left(- \sum_{n = N}^M P(A_n)\right).$

Now let $M \to \infty$. The partial sum $\sum_{n = N}^M P(A_n)$ diverges to $+\infty$ (because the full series does, and the partial sum from $N$ onward differs from the full sum by a finite quantity). So the exponential tends to $0$:

$P\!\left(\bigcap_{n \geq N} A_n^c\right) = \lim_{M \to \infty} P\!\left(\bigcap_{n = N}^M A_n^c\right) \leq \lim_{M \to \infty} \exp\!\left(- \sum_{n = N}^M P(A_n)\right) = 0.$

The first equality uses continuity of probability for decreasing intersections (Proposition 1(v) applied to complements). Since probabilities are non-negative, $P(\bigcap_{n \geq N} A_n^c) = 0$. $\blacksquare$

Take independent events with $P(A_n) = 1/n^\alpha$. The series $\sum_n 1/n^\alpha$ converges iff $\alpha > 1$ (the $p$-series test from Series Convergence & Tests). So:

• $\alpha > 1$: BC-I applies, $P(A_n \text{ i.o.}) = 0$. The events stop occurring after some finite point with probability one.
• $\alpha \leq 1$: BC-II applies, $P(A_n \text{ i.o.}) = 1$. The events recur forever.

The threshold is exactly at $\alpha = 1$ — the harmonic series. The accompanying interactive visualization sweeps $\alpha$ across the threshold and shows the cumulative-indicator trajectories diverging or stabilizing in real time.

Take all events equal: $A_n = A_1$ for every $n$, with $P(A_1) = p \in (0, 1)$. The events are not independent — they are perfectly dependent — and $\sum_n P(A_n) = \infty$ trivially. But

$P(A_n \text{ i.o.}) = P(A_1) = p,$

which is not $1$ in general. Independence is what makes the BC-II conclusion robust: under independence, the divergent sum forces the product $\prod (1 - P(A_n))$ to $0$; without it, the joint probabilities can conspire to keep the all-fail event positive.

There are partial substitutes — pairwise independence plus a Kolmogorov bound on covariances, exchangeability, etc. — but they are downstream of the full machinery of conditional expectation, and we defer them to Sigma-Algebras & Measures (forward) and to formalStatistics’s hypothesis-testing topic.

The Borel–Cantelli lemmas are special cases of a deeper structural fact: any tail event of an independent sequence — an event in the σ-algebra generated by $\{A_n, A_{n+1}, A_{n+2}, \ldots\}$ for every $N$ — has probability $0$ or $1$. The event $\{A_n \text{ i.o.}\}$ is a tail event by construction. Kolmogorov’s 0–1 law extends this to any tail event of an independent sequence, including the event “the Strong Law of Large Numbers holds for this sequence” (i.e., $\bar X_n \to \mu$). The full statement and proof require the measure-theoretic σ-algebra apparatus of Sigma-Algebras & Measures (forward) and is the entry point to the Strong Law and the law of the iterated logarithm.

Let $X$ be a non-negative random variable with finite expectation $E[X]$, and let $a > 0$. Then

$P(X \geq a) \leq \frac{E[X]}{a}.$

For $X \geq 0$ and $a > 0$, observe the pointwise inequality

$a \cdot \mathbf{1}_{\{X \geq a\}} \leq X.$

To see it: on the event $\{X \geq a\}$, the indicator is $1$, so the left-hand side is $a$, and $a \leq X$ by hypothesis; on the complement, the indicator is $0$, so the left-hand side is $0$, and $0 \leq X$ since $X \geq 0$. Taking expectations of both sides (using linearity and monotonicity of expectation),

$a \, P(X \geq a) = E[a \cdot \mathbf{1}_{\{X \geq a\}}] \leq E[X].$

Divide by $a > 0$. $\blacksquare$

For non-negative $X$, the tail-integral identity from Improper Integrals & Special Functions

$E[X] = \int_0^\infty P(X > t) \, dt$

says the area under the survival curve $t \mapsto P(X > t)$ equals the mean. Markov’s inequality says that no rectangle inscribed under the survival curve can have area greater than the total area:

$a \cdot P(X \geq a) \leq \int_0^\infty P(X > t) \, dt = E[X].$

The rectangle in question has width $a$ and height $P(X \geq a)$, and it fits under the survival curve because the survival function is non-increasing.

Let $X$ be a random variable with $E[X] = \mu$ and finite variance $\sigma^2 = \mathrm{Var}(X) < \infty$. Then for any $\epsilon > 0$:

$P(|X - \mu| \geq \epsilon) \leq \frac{\sigma^2}{\epsilon^2}.$

Apply Markov’s inequality to the non-negative random variable $Y = (X - \mu)^2$ at the threshold $a = \epsilon^2$:

$P(Y \geq \epsilon^2) \leq \frac{E[Y]}{\epsilon^2} = \frac{\mathrm{Var}(X)}{\epsilon^2} = \frac{\sigma^2}{\epsilon^2}.$

But $\{Y \geq \epsilon^2\} = \{(X - \mu)^2 \geq \epsilon^2\} = \{|X - \mu| \geq \epsilon\}$. So $P(|X - \mu| \geq \epsilon) \leq \sigma^2 / \epsilon^2$. $\blacksquare$

Let $X_1, X_2, \ldots, X_n$ be independent and identically distributed with mean $\mu$ and finite variance $\sigma^2$. Let $\bar X_n = \frac{1}{n} \sum_{i=1}^n X_i$ be the sample mean. By the linearity of expectation and the variance of an independent sum,

$E[\bar X_n] = \mu, \quad \mathrm{Var}(\bar X_n) = \frac{\sigma^2}{n}.$

Chebyshev applied to $\bar X_n$ gives, for any $\epsilon > 0$:

$P(|\bar X_n - \mu| \geq \epsilon) \leq \frac{\sigma^2}{n \epsilon^2}.$

As $n \to \infty$, the right-hand side tends to $0$, so $\bar X_n \to \mu$ in probability. This is the Weak Law of Large Numbers, derived from one inequality. The rate is polynomial in $n$: doubling $n$ halves the bound.

Hoeffding’s inequality (Theorem 7 below) replaces this polynomial rate with an exponential one when the $X_i$ are bounded — a strict improvement for moderate-to-large deviations.

For a Gaussian random variable $X \sim N(0, 1)$, the actual tail is $P(|X| \geq t) \leq 2 e^{-t^2 / 2}$ — exponentially decaying. Chebyshev gives only $1/t^2$ — polynomial. At $t = 3$, the Gaussian tail is $\approx 0.0027$, while Chebyshev says $\leq 1/9 \approx 0.111$ — off by nearly two orders of magnitude.

This gap between polynomial Chebyshev bounds and exponential true tails is what motivates Hoeffding’s inequality: when we know more about the random variable (boundedness, sub-Gaussian moment generating function), we can replace the polynomial decay with an exponential one. The MGF method developed in §8 is the standard route.

For a random variable $X$, the moment generating function (MGF) is

$M_X(t) = E[e^{tX}],$

defined for those $t \in \mathbb{R}$ at which the expectation is finite.

This is the only place in the topic where the MGF appears. We use it as a single technical device: $X$ has a small MGF $\Leftrightarrow$ $X$ has light tails. Markov’s inequality applied to the non-negative random variable $e^{tX}$ converts a bound on the MGF into a bound on $P(X \geq a)$. The rigorous Lebesgue-integral foundations of expectation, conditions for the MGF to exist in a neighborhood of $0$, and the Cramér–Chernoff method are developed in The Lebesgue Integral (forward) and in formalML’s Concentration Inequalities → formalML. Here we treat the MGF as a black box that produces the bound.

If $X$ is a random variable with $E[X] = 0$ and $a \leq X \leq b$ almost surely, then for every $t \in \mathbb{R}$:

$E[e^{tX}] \leq \exp\!\left(\frac{t^2 (b - a)^2}{8}\right).$

Proof sketch. The function $x \mapsto e^{tx}$ is convex. For $x \in [a, b]$, convexity gives the chord bound

$e^{tx} \leq \frac{b - x}{b - a} e^{ta} + \frac{x - a}{b - a} e^{tb}.$

Take expectations on both sides, using $E[X] = 0$:

$E[e^{tX}] \leq \frac{b}{b - a} e^{ta} - \frac{a}{b - a} e^{tb} =: e^{\phi(t)},$

where $\phi(t)$ is the logarithm of the right-hand side. Direct calculus shows $\phi(0) = 0$, $\phi'(0) = 0$, and $\phi''(t) \leq (b - a)^2 / 4$ uniformly in $t$. By Taylor’s theorem (see Taylor Series and Polynomial Approximation),

$\phi(t) \leq \frac{t^2 (b - a)^2}{8}.$

Exponentiating gives the claim. The full algebra is performed in the companion notebook. $\blacksquare$

Let $X_1, X_2, \ldots, X_n$ be independent random variables with $a_i \leq X_i \leq b_i$ almost surely. Let $S_n = \sum_{i=1}^n X_i$. Then for any $t > 0$: