Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 2.2.1 — the queueing proof of the pointwise ergodic theorem

Proved
PalmQueueing.Loynes.queueing_ergodic_theorem

by mikedeng1 · Oct 1, 2026 · Mathlib 0df444a (Lean v4.33.1)

ergodic-theorypalm-calculusqueueingstabilitystationary-process

Theorem 2.2.1. Whenever (P0,θ)(P^0, \theta)(P0,θ) is ergodic and both σ\sigmaσ and τ\tauτ are non-negative, not identically null, and integrable,

lim⁡n→∞∑i=0nσ∘θ−i∑i=0nτ∘θ−i  =  E0[σ]E0[τ],P0-a.s.\lim_{n \to \infty} \frac{\sum_{i=0}^{n} \sigma \circ \theta^{-i}}{\sum_{i=0}^{n} \tau \circ \theta^{-i}} \;=\; \frac{E^0[\sigma]}{E^0[\tau]} , \qquad P^0\text{-a.s.}n→∞lim​∑i=0n​τ∘θ−i∑i=0n​σ∘θ−i​=E0[τ]E0[σ]​,P0-a.s.

The direction of the argument is the point, and the section's title says so: "Queueing Proof of the Ergodic Theorem". The queueing construction of §2.2 — Loynes' monotone scheme, Hopf's lemma (2.2.18) and the stability criterion — yields the pointwise ergodic theorem rather than being derived from it. The ratio form is what that route naturally produces, since what the queue supplies is the comparison ∑i=1nσ∘θ−i≤∑i=1nτ∘θ−i+Mn\sum_{i=1}^n \sigma\circ\theta^{-i} \le \sum_{i=1}^n \tau\circ\theta^{-i} + M_n∑i=1n​σ∘θ−i≤∑i=1n​τ∘θ−i+Mn​ with Mn↑M∞<∞M_n \uparrow M_\infty < \inftyMn​↑M∞​<∞ whenever E0[σ]<E0[τ]E^0[\sigma] < E^0[\tau]E0[σ]<E0[τ]; a scaling argument over all aaa with aE0[σ]<E0[τ]aE^0[\sigma] < E^0[\tau]aE0[σ]<E0[τ] then gives the lim sup⁡\limsuplimsup bound E0[σ]/E0[τ]E^0[\sigma]/E^0[\tau]E0[σ]/E0[τ], and exchanging the roles of σ\sigmaσ and τ\tauτ gives the matching lim inf⁡\liminfliminf.

Mathlib's Ergodic is reused rather than a private notion of ergodicity. Mathlib has the mean (von Neumann) ergodic theorem but no pointwise one, so nothing here duplicates an existing result.

Preamble
import Mathlib

/-!
# Theorem 2.2.1: the queueing proof of the pointwise ergodic theorem (§2.2.5, p.90)
-/
Formal statement
namespace PalmQueueing.Loynes

open MeasureTheory Filter Topology

variable {Ω : Type*} [MeasurableSpace Ω]

/-- **Theorem 2.2.1** (§2.2.5, p.90). Whenever `(P⁰, θ)` is ergodic and both `σ` and `τ` are
non-negative, not identically null, and integrable,

`lim_{n→∞} ( Σ_{i=0}^{n} σ ∘ θ^{-i} ) / ( Σ_{i=0}^{n} τ ∘ θ^{-i} ) = E⁰[σ] / E⁰[τ]`,  `P⁰`-a.s.

The section's title is "Queueing Proof of the Ergodic Theorem", and the point is the direction of
the argument: the queueing construction of §2.2 — Loynes' monotone scheme, Hopf's lemma (2.2.18)
and the stability criterion — *yields* the pointwise ergodic theorem, rather than being derived
from it. The ratio form is the natural output of that route, since what the queue supplies is the
comparison `Σ σ ∘ θ^{-i} ≤ Σ τ ∘ θ^{-i} + M_n` with `M_n ↑ M_∞ < ∞`.

Mathlib's `Ergodic` is reused rather than a private notion; Mathlib has the *mean* ergodic theorem
but no pointwise one, so nothing here duplicates it. -/
theorem queueing_ergodic_theorem (P0 : Measure Ω) [IsProbabilityMeasure P0]
    (shift : Ω ≃ᵐ Ω) (herg : Ergodic shift P0)
    (sig tau : Ω → ℝ) (hsigmeas : Measurable sig) (htaumeas : Measurable tau)
    (hsig0 : ∀ ω, 0 ≤ sig ω) (htau0 : ∀ ω, 0 ≤ tau ω)
    (hsigNull : ¬ (∀ᵐ ω ∂P0, sig ω = 0)) (htauNull : ¬ (∀ᵐ ω ∂P0, tau ω = 0))
    (hsigInt : Integrable sig P0) (htauInt : Integrable tau P0) :
    ∀ᵐ ω ∂P0, Tendsto
      (fun n : ℕ =>
        (∑ i ∈ Finset.range (n + 1), sig ((shift.symm^[i]) ω)) /
        (∑ i ∈ Finset.range (n + 1), tau ((shift.symm^[i]) ω)))
      atTop (𝓝 ((∫ ω, sig ω ∂P0) / ∫ ω, tau ω ∂P0)) := by sorry

end PalmQueueing.Loynes
Source
Baccelli & Bremaud, Elements of Queueing Theory: Palm Martingale Calculus and Stochastic Recurrences, 2nd ed., Springer 2003, p. 90, Theorem 2.2.1
Human review
  • Endorsed by Shuze Chen · Oct 5, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 5, 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