Tutorials › Probability Theory (Graduate) › The Hewitt–Savage Zero–One Law

Home  /  Tutorials  /  Independence and Zero-One Laws

Independence and Zero-One Laws · Tutorial 224 of 946

The Hewitt–Savage Zero–One Law

Learn why finite-permutation invariance forces a zero–one probability, and how to apply the result to events defined by the values appearing in an iid sequence.

Intermediate 10 min read

What You'll Learn

  • Define finite-permutation invariance for events of an iid sequence
  • Prove the finite-coordinate approximation fact needed for the argument
  • Use a remote coordinate block to establish independence from finite-coordinate events
  • Deduce the Hewitt–Savage zero–one law
  • Apply the law to occurrence and supremum events

Why Finite Permutations Matter

An independent identically distributed sequence has no distinguished coordinate: any finite collection of coordinates has the same joint distribution after it is rearranged. Some events reflect this symmetry. For instance, whether a sequence contains a value in a particular set does not depend on the order in which its values appear.

The Hewitt–Savage zero–one law gives a striking conclusion for such events. If an event is measurable from the sequence and is unchanged by every permutation that moves only finitely many coordinates, then its probability cannot lie strictly between zero and one.

Central idea: Approximate the event using finitely many coordinates, move those coordinates to a remote block by a finite permutation, and use independence between that block and the original coordinates.

Finite-Permutation Invariance

Let \((X_n)_{n\in\mathbb{N}}\) be an iid sequence of real-valued random variables. Write \(\mathbb{R}^{\mathbb{N}}\) for the sequence space, and let \(\mu\) be the distribution of the random sequence \(X=(X_1,X_2,\ldots)\). A finite permutation is a bijection \(\pi:\mathbb{N}\to\mathbb{N}\) that fixes all but finitely many indices. It acts on a sequence \(x=(x_1,x_2,\ldots)\) by rearranging its coordinates.

$$ \tau_\pi(x)=(x_{\pi(1)},x_{\pi(2)},\ldots). $$
Definition: A measurable event \(E\subseteq\mathbb{R}^{\mathbb{N}}\) is invariant under finite permutations if, for every finite permutation \(\pi\), a sequence belongs to \(E\) exactly when its rearrangement \(\tau_\pi(x)\) belongs to \(E\). Equivalently, \(\tau_\pi^{-1}(E)=E\) for every such \(\pi\). The corresponding event for the random sequence is \(A=\{X\in E\}\).

An iid sequence has a distribution unchanged by each finite permutation: \(\tau_\pi(X)\) has the same distribution as \(X\). This follows from the identical distributions and independence of the coordinates. We will also use that disjoint finite blocks of coordinates are independent, as are the sigma-algebras they generate.

Worked Example: Infinitely Many Successes

Let \(X_n\) be iid Bernoulli random variables with success probability \(p\), and let \(E\) be the event that \(X_n=1\) for infinitely many \(n\). A finite permutation can change only finitely many positions, so it cannot change whether successes occur infinitely often. Thus \(E\) is invariant under finite permutations, and the Hewitt–Savage law says its probability is zero or one.

Here we can also calculate the probability directly. If \(p=0\), every \(X_n=0\) almost surely, so \(P(E)=0\). If \(p>0\), for each fixed \(N\),

$$ P(X_n=0\text{ for all }n\ge N) =\lim_{m\to\infty}(1-p)^{m-N+1} =0. $$

The event of only finitely many successes is the union, over \(N\in\mathbb{N}\), of the events that there are no successes from \(N\) onward. Each has probability zero, so the union has probability zero. Therefore \(P(E)=1\) when \(p>0\).

A Finite-Coordinate Approximation Fact

The proof needs a way to replace a measurable event by one that depends on finitely many coordinates. Let \(\mathcal{F}=\sigma(X_1,X_2,\ldots)\), and let \(\mathcal{A}\) be the algebra of events depending on finitely many coordinates. That is, an event in \(\mathcal{A}\) can be described using a measurable condition on \(X_1,\ldots,X_k\) for some finite \(k\). This algebra generates \(\mathcal{F}\).

Lemma: For every \(G\in\mathcal{F}\) and every \(\varepsilon>0\), there is an event \(C\in\mathcal{A}\) such that \(P(G\triangle C)<\varepsilon\), where \(G\triangle C=(G\setminus C)\cup(C\setminus G)\).
Proof. Let \(\mathcal{D}\) be the class of events \(G\in\mathcal{F}\) that can be approximated in probability by events in \(\mathcal{A}\) to every positive accuracy. The class \(\mathcal{D}\) contains \(\mathcal{A}\). If \(G\in\mathcal{D}\), then \(G^c\in\mathcal{D}\), because \(P(G^c\triangle C^c)=P(G\triangle C)\).

To check closure under countable unions, take \(G_1,G_2,\ldots\in\mathcal{D}\) and set \(G=\bigcup_{i=1}^{\infty}G_i\). By continuity of probability for increasing unions, choose \(m\) such that

$$ P\left(G\setminus\bigcup_{i=1}^{m}G_i\right)<\frac{\varepsilon}{2}. $$

For \(1\le i\le m\), choose \(C_i\in\mathcal{A}\) with \(P(G_i\triangle C_i)<\varepsilon/(2m)\). The event \(C=\bigcup_{i=1}^{m}C_i\) belongs to \(\mathcal{A}\), and

$$ P(G\triangle C) \le P\left(G\setminus\bigcup_{i=1}^{m}G_i\right) +\sum_{i=1}^{m}P(G_i\triangle C_i) <\varepsilon. $$

Thus \(\mathcal{D}\) is a sigma-algebra containing \(\mathcal{A}\). Since \(\mathcal{A}\) generates \(\mathcal{F}\), every event in \(\mathcal{F}\) belongs to \(\mathcal{D}\). \(\square\)

The Hewitt–Savage Zero–One Law

Theorem (Hewitt–Savage zero–one law): Let \((X_n)_{n\in\mathbb{N}}\) be an iid sequence, and let \(A\in\sigma(X_1,X_2,\ldots)\) be invariant under every finite permutation of its coordinates. Then \(P(A)\in\{0,1\}\).
Proof. First consider any event \(B\) depending on the first \(k\) coordinates, where \(k\in\mathbb{N}\). Since \(A\in\sigma(X_1,X_2,\ldots)\), the approximation lemma gives an event \(C\), depending on \(X_1,\ldots,X_n\) for some \(n\), such that \(P(A\triangle C)<\varepsilon\). We may take \(n\ge k\), by allowing \(C\) to ignore any additional coordinates.

Let \(\pi\) interchange \(i\) and \(n+i\) for each \(1\le i\le n\), fixing all other indices. Transform \(C\) by this permutation to obtain an event \(C'\) depending only on \(X_{n+1},\ldots,X_{2n}\). Because \(A\) is invariant and the distribution of the sequence is unchanged by \(\pi\),

$$ P(A\triangle C')=P(A\triangle C)<\varepsilon. $$

The events \(C'\) and \(B\) depend on disjoint blocks of an iid sequence. They are independent, so \(P(C'\cap B)=P(C')P(B)\). The approximations give

$$ \begin{aligned} |P(A\cap B)-P(A)P(B)| &\le |P(A\cap B)-P(C'\cap B)|\\ &\quad+|P(C')P(B)-P(A)P(B)|\\ &\le P(A\triangle C')+|P(C')-P(A)|\\ &<2\varepsilon. \end{aligned} $$

As \(\varepsilon>0\) was arbitrary, \(P(A\cap B)=P(A)P(B)\) for every event \(B\) depending on finitely many coordinates.

Now take any \(B\in\sigma(X_1,X_2,\ldots)\). By the approximation lemma, there are finite-coordinate events \(B_j\) such that \(P(B\triangle B_j)\to0\). Since \(A\) is independent of every \(B_j\), and

$$ |P(A\cap B)-P(A\cap B_j)|\le P(B\triangle B_j), \qquad |P(B)-P(B_j)|\le P(B\triangle B_j), $$

passing to the limit gives \(P(A\cap B)=P(A)P(B)\). In particular, \(A\) is independent of itself. Hence \(P(A)=P(A\cap A)=P(A)^2\). The only solutions in \([0,1]\) are \(P(A)=0\) and \(P(A)=1\). \(\square\)

Worked Applications

Worked Example: At Least One Observation in a Set

Let \(X_n\) be iid with common distribution \(\nu\), and let \(D\subseteq\mathbb{R}\) be measurable. The event \(E=\{\text{there exists }n\text{ with }X_n\in D\}\) is unchanged by finite permutations. Set \(q=\nu(D)\). For each \(m\), independence gives

$$ P(X_1,\ldots,X_m\notin D)=(1-q)^m. $$

The event of never entering \(D\) is the decreasing intersection of these finite avoidance events. Therefore its probability is \(\lim_{m\to\infty}(1-q)^m\). If \(q=0\), this limit is \(1\), and \(P(E)=0\). If \(q>0\), the limit is \(0\), and \(P(E)=1\). The calculation agrees with the zero–one conclusion.

Worked Example: The Sequence Is Bounded Above by a Fixed Level

Let \(X_n\) be iid standard normal random variables, and fix \(c\in\mathbb{R}\). The event \(E=\{X_n\le c\text{ for every }n\}\) is invariant under finite permutations. Write \(\Phi(c)=P(X_1\le c)\). Independence gives, for every \(m\),

$$ P(X_1\le c,\ldots,X_m\le c)=\Phi(c)^m. $$

Since \(\Phi(c)<1\) for every finite \(c\), the probability of the decreasing intersection over all \(m\) is \(\lim_{m\to\infty}\Phi(c)^m=0\). Thus an iid standard normal sequence is almost surely not bounded above by any one fixed finite level. Each individual event is covered by the Hewitt–Savage law; the calculation identifies its probability as zero.

What the Invariance Assumption Does—and Does Not—Say

The theorem concerns invariance under every finite permutation, not merely invariance under a particular rearrangement or under shifts of the indices. Its other essential hypothesis is measurability from the sequence itself. An event involving additional randomness outside \(\sigma(X_1,X_2,\ldots)\) is not covered just because its description appears symmetric in the \(X_n\).

The proof also explains why the result is stronger than a direct appeal to the invariance of the iid distribution. Invariance of the distribution alone says that a rearranged sequence has the same law. The argument uses invariance of the event as well: it allows a finite-coordinate approximation to the event to be moved to a disjoint block while remaining close to the original event. Independence then forces the event to be independent of every finite-coordinate event, and hence of itself.

When checking an application, identify the event precisely, verify that changing finitely many coordinate positions leaves membership unchanged, and confirm that the event belongs to the sigma-algebra generated by the sequence. The theorem determines whether the probability is zero or one; additional information may be needed to decide which value occurs.

Check Your Understanding

Use the definition and proof to check each point.

  1. Why does moving finitely many coordinates not change the event that successes occur infinitely often?
  2. In the proof, why is the transformed approximation \(C'\) independent of an event depending on the first \(k\) coordinates?
  3. Where is invariance of \(A\) used to compare \(P(A\triangle C')\) with \(P(A\triangle C)\)?
  4. Why does independence of \(A\) from every event in \(\sigma(X_1,X_2,\ldots)\) imply \(P(A)=P(A)^2\)?
  5. For iid variables with \(P(X_1\in D)=q>0\), what is the probability that at least one observation lies in \(D\), and why?

Previous

Next

Back to Tutorials
Clinical Biostats