Zero–One Laws

Some events have probability $0$ or $1$ for structural reasons — no computation with the underlying distribution is needed, only the observation that the event does not depend on any finite amount of the data. These results are the sharpest illustration of a recurring theme: a great deal is settled by the shape of the measure rather than by its values.

References: Durrett, Probability, §2.5; Kallenberg, Foundations, ch. 3; Williams, Probability with Martingales, ch. 4, 14.

1. Tail Events

Let $X_1,X_2,\dots$ be random variables and ${\mathcal{F}}_n=\sigma (X_n,X_{n+1},\dots )$ the $\sigma$-algebra generated by the sequence from $n$ onwards.

Definition. The tail $\sigma$-algebra is $\mathcal{T}=\bigcap _{n=1}^{\infty }{\mathcal{F}}_n$. Its members are tail events: events unaffected by altering any finite number of the $X_i$.

Examples of tail events:

• $\{{\sum }_k{X}_k\text{ converges}\}$ — changing finitely many terms cannot change convergence;
• $\{X_k\in B\text{ infinitely often}\}$;
• $\{{\lim }_k{\bar{X}}_n\text{ exists}\}$ and $\{{\mathrm{limsup}}_n{\bar{X}}_n\le c\}$ — the averages are not tail-measurable individually, but their limiting behaviour is, since finitely many terms contribute $O(1/n)$.

Not tail events: $\{X_1=0\}$, $\{{\sum }_k{X}_k\le 3\}$ (the value of a convergent sum does depend on early terms).

2. Kolmogorov's Zero–One Law

Theorem. If $X_1,X_2,\dots$ are independent, then every tail event has probability $0$ or $1$, and every $\mathcal{T}$-measurable random variable is a.s. constant.

Proof. Let $A\in \mathcal{T}$. For each $n$, $A\in {\mathcal{F}}_{n+1}$, which is independent of $\sigma (X_1,\dots ,X_n)$; so $A$ is independent of the $\pi$-system ${\bigcup }_n\sigma (X_1,\dots ,X_n)$, hence — by the $\pi$–$\lambda$ argument of independence.md §2 — independent of the $\sigma$-algebra it generates, namely $\sigma (X_1,X_2,\dots )\supseteq \mathcal{T}$. So $A$ is independent of itself: $P(A)=P(A\cap A)=P(A{)}^2$, forcing $P(A)\in \{0,1\}$. $\square$

The self-independence trick is the whole proof, and it is worth pausing on: the tail $\sigma$-algebra is simultaneously inside the sequence's $\sigma$-algebra and independent of every finite piece of it, and those two facts are only compatible if it is trivial.

Consequences, all immediate:

• ${\sum }_k{X}_k$ converges a.s. or diverges a.s. — never in between.
• ${\mathrm{limsup}}_n{\bar{X}}_n$ is an a.s. constant (possibly $\pm \infty$). This is why the strong law can have a deterministic limit at all (laws-of-large-numbers.md): the zero–one law tells us the limit is a constant before any computation identifies it as $\mu$.
• The radius of convergence of ${\sum }_k{X}_k{z}^k$ is a.s. constant.
• The second Borel–Cantelli lemma (independence.md §5) is the special case $A=\{A_k\text{ i.o.}\}$ with the dichotomy resolved by the divergence criterion.

3. Hewitt–Savage

Independence plus identical distribution gives a stronger triviality, on a larger $\sigma$-algebra.

Definition. An event is exchangeable if it is invariant under every finite permutation of the coordinates. These form the exchangeable $\sigma$-algebra $\mathcal{E}\supseteq \mathcal{T}$.

Hewitt–Savage zero–one law. If $X_1,X_2,\dots$ are i.i.d., every exchangeable event has probability $0$ or $1$.

Proof idea. Approximate an exchangeable $A$ by an event $A_n$ depending on the first $n$ coordinates; apply the permutation swapping the first $n$ with the next $n$, which preserves $P$ (i.i.d.) and fixes $A$; conclude $P(A\cap \pi A_n)\to P(A{)}^2$ and also $\to P(A)$. $\square$

$\mathcal{E}$ is strictly larger than $\mathcal{T}$: the event $\{S_n=0\text{ for some }n\}$ for a simple random walk is exchangeable but not tail (changing $X_1$ can change it). So Hewitt–Savage decides things Kolmogorov cannot — for instance that a simple random walk on $\mathbb{Z}$ is either recurrent or transient with probability one, never something in between.

The hypothesis is exactly identical distribution. For merely independent, non-identically-distributed sequences the exchangeable $\sigma$-algebra can be non-trivial. And if independence is dropped in favour of exchangeability alone, triviality fails completely: an exchangeable sequence is a mixture of i.i.d. ones, and the mixing parameter is an exchangeable random variable that is not constant — see exchangeability-de-finetti.md. The two theorems are the extreme and general cases of one picture.

4. Lévy's Zero–One Law

A martingale-theoretic statement that contains the others, and explains them.

Theorem (Lévy). Let ${\mathcal{F}}_n\uparrow {\mathcal{F}}_{\infty }=>\sigma ({\bigcup }_n{\mathcal{F}}_n)$ and $A\in {\mathcal{F}}_{\infty }$. Then

$$P(A\mid {\mathcal{F}}_n)\stackrel{\text{a.s.}}{\to }{1}_A.$$

This is the martingale convergence theorem applied to the uniformly integrable martingale $M_n=E[1_A\mid {\mathcal{F}}_n]$ (martingales.md). Read it as: accumulated information settles every question in the limit. Kolmogorov's law follows by taking $A$ tail: then $P(A\mid {\mathcal{F}}_n)=P(A)$ for every $n$ by independence, and the limit $1_A$ must equal the constant $P(A)$ a.s.

5. What These Results Do and Do Not Show

• They are theorems about the measure, not predictions. "Either the series converges a.s. or it diverges a.s." does not tell you which; identifying the value requires the actual distribution (Kolmogorov's three-series theorem, for the convergence example).
• The dichotomy is a consequence of independence, which is a modelling assumption (independence.md §6). Drop it and the dichotomy goes: the whole content of de Finetti's theorem is that exchangeable sequences have a genuinely random tail.
• They explain why deterministic answers are available at all. Every limit statement in Part B — the strong law's limit, the CLT's normalizing constants, the law of the iterated logarithm's envelope — is a constant because a zero–one law says it must be. The subsequent work only computes which constant.

6. Where This Is Used

• Laws of large numbers — the limit is constant before it is identified; the ergodicity of the i.i.d. shift is §2.
• Independence §5 — Borel–Cantelli as the prototype.
• Exchangeability and de Finetti — what replaces §3 when independence is dropped.
• Martingales — §4, and the general machinery behind all of it.