What is Independence?

Example 21.21 (Independence read off a product structure)

Roll two fair dice: $\Omega = \intint16^2$ with uniform weights. Let $A = {}$“first die even” and $B = {}$“second die at least $5$”. Counting: $\abs A = 3\cdot6 = 18$, $\abs B = 6\cdot2 = 12$, $\abs{A\cap B} = 3\cdot2 = 6$, so

independent, and the mechanism is visible — $A$ constrains only the first coordinate, $B$ only the second, and the uniform measure on a product set makes coordinate counts multiply. Every claim of the type “events depending on disjoint groups of tosses are independent” (used massively in the weekend problem) is this computation, wearing more indices.

Example 21.8 (The union bound: crude but indestructible)

Subadditivity with finitely many events — the union bound — trades precision for universality. For the birthday problem with $23$ people, bounding the collision probability by the sum over pairs gives

against the true $0.507$: off by a wide margin, because collisions overlap. Yet the bound needs no independence, no joint law, nothing but the pair probabilities — which is why, in the weekend problem and throughout Chapter 22, the union bound is the first tool drawn: when it happens to be small, the matter is settled with no further modelling.

Example 21.15 (The birthday collision, by the chain rule)

With $n$ people whose birthdays are independent and uniform over $365$ days, let $D_n = {}$“all $n$ birthdays differ”. Conditioning person by person (chain rule):

each new person having to avoid the $k$ days already taken. For $n = 23$: $\P(D_{23}) \approx 0.493$ — a shared birthday is already more likely than not. The heuristic that explains the smallness of $23$: taking logarithms, $-\ln \P(D_n) \approx \sum_{k<n}\frac k{365} = \frac{\binom n2}{365}$, and $\binom{23}2 = 253$ gives $253/365 \approx 0.693 \approx \ln 2$. What matters is the number of pairs, which grows quadratically: collision problems live on the scale $n \sim \sqrt{365}$, not $n \sim 365$ — the birthday paradox is a square root in disguise.

Example 22.7 (The birthday problem, honestly)

Among $n$ people with independent, uniform birthdays over $N = 365$ days, the probability that all birthdays differ is

by iterated conditioning (or directly: the favorable $N(N-1)\cdots(N - n + 1)$ over the total $N^n$, a counting argument the product formula of independence makes rigorous). Taking logarithms and using $-\ln(1 - x) = x + O(x^2)$:

The tipping point $p_n = \frac12$ sits at $n \approx \sqrt{2N\ln2} \approx 1.18\sqrt N$: for $N = 365$, $n = 23$ ($p_{23} = 0.4927$). Two morals. First, collisions among $n$ items in $N$ boxes appear at the scale $n \sim \sqrt N$, not $n \sim N$ — the birthday scaling that governs hash collisions and the $\sqrt N$ cost of birthday attacks in cryptography. Second, the computation is a template: the $\binom n2$ pair-collision events are not independent, yet the answer behaves as if they were ($\eu^{-\binom n2/N}$ is exactly the independent-pairs heuristic) — a first instance of the Poisson approximation made rigorous in Chapter 23’s weekend problem (Le Cam’s inequality).

Example 22.14 (What the strong law buys)

(a) Frequencies: for i.i.d. coin flips, the observed frequency of heads converges a.s. to $p$ — the empirical justification of probability itself. (b) Monte Carlo: for $g \in L^1(\intcc01)$ and $(U_n)$ i.i.d. uniform (Theorem 22.6), $\frac1n\sum_{k\leq n}g(U_k) \to \int_0^1g$ a.s.: integrals by sampling, in any dimension, at the dimension-independent rate $\sim n^{-1/2}$ made precise in Chapter 23. (c) Normal numbers: almost every real number has, in its binary expansion, asymptotic frequency $\frac12$ of ones (apply the strong law to the digit variables of Theorem 22.6) — Borel’s theorem, a statement about everyday numbers proved by measure: Problem 22.1 completes it in all bases.