Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 1 — strong law of large numbers along a predictably selected subsequence

Proved
KMNewsvendor.optional_skipping_slln

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

optional-skippingprobabilitystrong-law

Let D1,D2,…D_1,D_2,\dotsD1​,D2​,… be independent real random variables, all distributed like DDD, and let Ft=σ(D1,…,Dt)\mathcal F_t=\sigma(D_1,\dots,D_t)Ft​=σ(D1​,…,Dt​) (F0\mathcal F_0F0​ trivial). Let ξ1,ξ2,⋯∈{0,1}\xi_1,\xi_2,\dots\in\{0,1\}ξ1​,ξ2​,⋯∈{0,1} be selection indicators such that each ξt\xi_tξt​ is Ft−1\mathcal F_{t-1}Ft−1​-measurable, i.e. a deterministic measurable function of D1,…,Dt−1D_1,\dots,D_{t-1}D1​,…,Dt−1​, and such that almost surely ξt=1\xi_t=1ξt​=1 for infinitely many ttt. Let f:R→Rf:\mathbb R\to\mathbb Rf:R→R be measurable with f(D)f(D)f(D) integrable. Then, almost surely,

lim⁡T→∞∑t=1Tξt f(Dt)∑t=1Tξt=E[f(D)].\lim_{T\to\infty}\frac{\sum_{t=1}^{T}\xi_t\,f(D_t)}{\sum_{t=1}^{T}\xi_t}=E[f(D)].T→∞lim​∑t=1T​ξt​∑t=1T​ξt​f(Dt​)​=E[f(D)].

The subsequence of selected demands is chosen adaptively, after seeing the earlier demands, and the strong law still holds along it. This is the probabilistic engine of the paper: the censoring decisions of an inventory policy are exactly such predictable selections.

Formalization Note Lean's index ttt is the source's t+1t+1t+1; ξ t is a Boolean given by a measurable function of D 0, …, D (t-1) (for t=0t=0t=0, a constant). "P[∑tξt=∞]=1P[\sum_t\xi_t=\infty]=1P[∑t​ξt​=∞]=1" is "almost surely, frequently ξ t = true". The source's hypothesis "E[f(D)]<∞E[f(D)]<\inftyE[f(D)]<∞" is formalized as integrability of f(D)f(D)f(D), which makes E[f(D)]E[f(D)]E[f(D)] a finite real number. For the finitely many TTT with an empty selection the Lean quotient is 0/0=00/0=00/0=0, which does not affect the limit.

Preamble
import Mathlib
open MeasureTheory ProbabilityTheory Filter Finset Topology
Formal statement
namespace KMNewsvendor

/-- Lemma 1 (p. 934): the strong law of large numbers along a predictably selected subsequence.
`ξ t` (Lean period `t`, the paper's `ξ_{t+1}`) is a deterministic measurable function of
the demands `D i`, `i < t`; infinitely many periods are selected almost surely; `f (D)` is integrable. -/
theorem optional_skipping_slln {Ω : Type*} [MeasurableSpace Ω] (μ : Measure Ω)
    [IsProbabilityMeasure μ]
    (D : ℕ → Ω → ℝ) (hmeas : ∀ t, Measurable (D t)) (hindep : iIndepFun D μ)
    (hident : ∀ t, IdentDistrib (D t) (D 0) μ μ)
    (ξ : ℕ → Ω → Bool)
    (hξ : ∀ t, ∃ g : (Fin t → ℝ) → Bool, Measurable g ∧ ξ t = fun ω => g (fun i => D i ω))
    (hinf : ∀ᵐ ω ∂μ, ∃ᶠ t in atTop, ξ t ω = true)
    (f : ℝ → ℝ) (hf : Measurable f) (hint : Integrable (fun ω => f (D 0 ω)) μ) :
    ∀ᵐ ω ∂μ, Tendsto (fun T : ℕ =>
        (∑ t ∈ range T, if ξ t ω = true then f (D t ω) else 0) /
          (((range T).filter (fun t => ξ t ω = true)).card : ℝ))
      atTop (𝓝 (∫ ω, f (D 0 ω) ∂μ)) := by sorry

end KMNewsvendor
Source
Huh, Levi, Rusmevichientong, Orlin, Adaptive Data-Driven Inventory Control with Censored Demand Based on Kaplan-Meier Estimator, Oper. Res. 59(4) (2011), doi:10.1287/opre.1100.0906, p. 934, Lemma 1
Read-back

What the Lean code literally says, in plain math · claude-opus-5-5

Setting.

  • (Ω,F,μ)(\Omega,\mathcal F,\mu)(Ω,F,μ) is a probability space.
  • D0,D1,⋯:Ω→RD_0,D_1,\dots:\Omega\to\mathbb RD0​,D1​,⋯:Ω→R are measurable, mutually independent, and each has the same distribution as D0D_0D0​ under μ\muμ.
  • ξ0,ξ1,⋯:Ω→{true,false}\xi_0,\xi_1,\dots:\Omega\to\{\text{true},\text{false}\}ξ0​,ξ1​,⋯:Ω→{true,false} are selection indicators.

Hypotheses.

  1. For every ttt there is a measurable gt:Rt→{true,false}g_t:\mathbb R^t\to\{\text{true},\text{false}\}gt​:Rt→{true,false} with ξt(ω)=gt(D0(ω),…,Dt−1(ω))\xi_t(\omega)=g_t(D_0(\omega),\dots,D_{t-1}(\omega))ξt​(ω)=gt​(D0​(ω),…,Dt−1​(ω)) for all ω\omegaω. So ξt\xi_tξt​ is determined by the strictly earlier values. In particular, ξ0\xi_0ξ0​ is a constant, since R0\mathbb R^0R0 is a single point.
  2. For μ\muμ-almost every ω\omegaω, ξt(ω)=true\xi_t(\omega)=\text{true}ξt​(ω)=true for infinitely many ttt.
  3. f:R→Rf:\mathbb R\to\mathbb Rf:R→R is measurable, and f(D0)f(D_0)f(D0​) is μ\muμ-integrable.

Conclusion. For μ\muμ-almost every ω\omegaω,

∑t<T, ξt(ω)=truef(Dt(ω))#{t<T:ξt(ω)=true}  →T→∞  ∫Ωf(D0) dμ.\frac{\sum_{t<T,\ \xi_t(\omega)=\text{true}} f(D_t(\omega))}{\#\{t<T:\xi_t(\omega)=\text{true}\}}\;\xrightarrow[T\to\infty]{}\;\int_\Omega f(D_0)\,d\mu .#{t<T:ξt​(ω)=true}∑t<T, ξt​(ω)=true​f(Dt​(ω))​T→∞​∫Ω​f(D0​)dμ.

Degenerate cases. When no t<Tt<Tt<T is selected (for example T=0T=0T=0), the quotient has denominator 000 and takes the value 000. By hypothesis 2, this happens for only finitely many TTT almost surely, so it does not affect the limit.

Human review
  • Endorsed by Shuze Chen · Oct 21, 2026

    Confirmed by the moderator at approval.

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