Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 2.5.4 — the Hewitt-Savage 0-1 law

Proved
DurrettProbability.hewitt_savage_zero_one

by naimengye · Sep 18, 2026 · Mathlib 0df444a (Lean v4.33.1)

probabilitypure-math

Let X1,X2,…X_1,X_2,\dotsX1​,X2​,… be independent and identically distributed, realized as the coordinates of the sequence space SNS^{\mathbb{N}}SN under the infinite product of copies of one law. An event AAA is permutable when rearranging finitely many coordinates does not change it: for every bijection σ\sigmaσ of N\mathbb{N}N fixing all but finitely many indices, {ω:ω∘σ∈A}=A\{\omega:\omega\circ\sigma\in A\}=A{ω:ω∘σ∈A}=A. Then

P(A)∈{0,1}.\mathbb{P}(A)\in\{0,1\}.P(A)∈{0,1}.

This strengthens Kolmogorov's 0-1 law in the i.i.d. case. Every tail event is permutable, since a permutation of the first nnn coordinates cannot affect an event determined by the coordinates beyond nnn; but the converse fails, and the standard witness is {Sn∈B infinitely often}\{S_n\in B\text{ infinitely often}\}{Sn​∈B infinitely often}, which is permutable — because Sn(ω)=Sn(σω)S_n(\omega)=S_n(\sigma\omega)Sn​(ω)=Sn​(σω) for large nnn — but not a tail event. So the exchangeable σ-field is strictly larger than the tail σ-field, and the theorem says that for an i.i.d. sequence both are trivial.

The consequences are the useful part: for a random walk with i.i.d. steps, statements like "lim sup⁡nSn/cn≥1\limsup_n S_n/c_n\ge1limsupn​Sn​/cn​≥1" or "the walk visits BBB infinitely often" have probability 000 or 111, with no further argument.

Formalization Note The sequence space is the countable product N→S\mathbb{N}\to SN→S carrying the infinite product measure, so "i.i.d." is built into the setting rather than hypothesised. A permutable event is given by its invariance property directly; the fact that such events form a σ-field is not needed for the statement and is not asserted.

Preamble
import Mathlib
import Definitions.Def_DurrettProbability_Series

open MeasureTheory ProbabilityTheory Filter
Formal statement
namespace DurrettProbability

theorem hewitt_savage_zero_one {S : Type*} [MeasurableSpace S] (μ : Measure S)
    [IsProbabilityMeasure μ] (A : Set (ℕ → S)) (hA : IsPermutable A) :
    (Measure.infinitePi (fun _ : ℕ => μ)) A = 0
      ∨ (Measure.infinitePi (fun _ : ℕ => μ)) A = 1 := by sorry

end DurrettProbability
Source
Durrett, Probability: Theory and Examples, Version 5 (11 January 2019), p. 82 (PDF p. 90), Theorem 2.5.4: 'Hewitt-Savage 0-1 law. If X_1, X_2, ... are i.i.d. and A is in the exchangeable sigma-field E then P(A) is 0 or 1.' The definitions on the same page: 'A finite permutation of N = {1, 2, ...} is a map pi from N onto N so that pi(i) != i for only finitely many i. ... An event A is permutable if pi^{-1} A = {omega : pi omega in A} is equal to A for any finite permutation pi, or in other words, if its occurrence is not affected by rearranging finitely many of the random variables. The collection of permutable events is a sigma-field. It is called the exchangeable sigma-field and denoted by E.' sha256 aeac36cbf5e44c53d69fa60a2d29a393e2d0e8c955ee103bd845d925fd910886
Human review
  • Endorsed by Shuze Chen · Sep 25, 2026

    Confirmed by the moderator at approval.

  • Endorsed by naimengye · Sep 25, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me