Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proof of Theorem 1, p. 765 — the case i = 1: θ^n_1 → θ*_1 a.s. and E|θ^n_1 − θ*_1|² ≤ Cγ_n^β

Disproved
AdaptiveProtection.Convergence.theorem1_case_one

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

almost-sure-convergencep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1revenue-managementrobbins-monrostochastic-approximation

Work under the hypotheses of Theorem 1: k≥1k \ge 1k≥1 protection levels, fares f1>⋯>fk+1>0f_1 > \cdots > f_{k+1} > 0f1​>⋯>fk+1​>0, independent nonnegative class demands with continuous distributions, step sizes γn=A/(n+B)\gamma_n = A/(n+B)γn​=A/(n+B) with A>0A > 0A>0, B≥0B \ge 0B≥0, an arbitrary initial vector θ1\theta^1θ1, a vector θ∗\theta^*θ∗ satisfying the optimality condition (3) P(Ai(θ∗,X))=ri+1P(A_i(\theta^*, X)) = r_{i+1}P(Ai​(θ∗,X))=ri+1​ for i=1,…,ki = 1, \dots, ki=1,…,k, and the assumptions A1 (bounded support), A2 (in the windowed form described below) and A3 (Lipschitz partial-sum distributions). Then the first protection level converges almost surely,

θ1n→θ1∗(a.s.),\theta^n_1 \to \theta^*_1 \quad \text{(a.s.)},θ1n​→θ1∗​(a.s.),

and there are β>0\beta > 0β>0 and CCC such that, for all n≥1n \ge 1n≥1, ∣θ1n−θ1∗∣2|\theta^n_1 - \theta^*_1|^2∣θ1n​−θ1∗​∣2 is integrable and

E∣θ1n−θ1∗∣2≤Cγnβ.E|\theta^n_1 - \theta^*_1|^2 \le C \gamma_n^{\beta}.E∣θ1n​−θ1∗​∣2≤Cγnβ​.

This is the base case of the induction on fare classes that proves Theorem 1: since A1(θ,X)={X1>θ1}A_1(\theta, X) = \{X_1 > \theta_1\}A1​(θ,X)={X1​>θ1​} depends on θ1\theta_1θ1​ only, (θ1n)(\theta^n_1)(θ1n​) is a scalar Robbins–Monro process.

Formalization Note The page asserts the rate "for all 0<β<10 < \beta < 10<β<1", citing Benveniste et al.; this is false in general (with h1h_1h1​ of slope exactly δ\deltaδ at θ1∗\theta^*_1θ1∗​ and 2δA<12\delta A < 12δA<1 the error decays like n−2δAn^{-2\delta A}n−2δA), and Theorem 1 needs only some β>0\beta > 0β>0, which is what is stated. A2 is pinned as in the goal theorem: for every radius R>0R > 0R>0 there is δR>0\delta_R > 0δR​>0 with (t−θi∗)hi(θ1∗,…,θi−1∗,t)≥δR∣t−θi∗∣2(t - \theta^*_i)h_i(\theta^*_1, \dots, \theta^*_{i-1}, t) \ge \delta_R |t - \theta^*_i|^2(t−θi∗​)hi​(θ1∗​,…,θi−1∗​,t)≥δR​∣t−θi∗​∣2 whenever ∣t−θi∗∣≤R|t - \theta^*_i| \le R∣t−θi∗​∣≤R. Lean's index nnn is the paper's n+1n + 1n+1.

Preamble
import Mathlib
import Definitions.Def_NestedSeatAlloc_ProbCond_Model
import Definitions.Def_AdaptiveProtection_Convergence_Setting

open MeasureTheory Filter Topology
Formal statement
namespace AdaptiveProtection.Convergence

/-- The case `i = 1` of the proof of Theorem 1 (p. 765): the first coordinate is a scalar
Robbins–Monro process, converges a.s. to `θ*_1`, and has mean-square rate `C γ_n^β` for some
`β > 0`. The page claims the rate "for all 0 < β < 1"; that is false in general (with
`h_1` of slope `δ` at `θ*_1` and `2δA < 1` the error decays like `n^{−2δA}`), and Theorem 1 uses
only the existence of one `β > 0`, which is what is stated here. -/
theorem theorem1_case_one
    (k : ℕ) (hk : 1 ≤ k) (f : ℕ → ℝ) (hf : ∀ i, 1 ≤ i → i ≤ k → f (i + 1) < f i)
    (hfpos : 0 < f (k + 1))
    (ν : ℕ → Measure ℝ) [∀ i, IsProbabilityMeasure (ν i)]
    (hnonneg : ∀ i, 1 ≤ i → i ≤ k + 1 → ∀ᵐ t ∂(ν i), 0 ≤ t)
    (hcont : ∀ i, 1 ≤ i → i ≤ k + 1 → NullSingletonClass (ν i))
    (A B : ℝ) (hA : 0 < A) (hB : 0 ≤ B)
    (θ₁ θstar : ℕ → ℝ)
    (hopt : ∀ i, 1 ≤ i → i ≤ k → (flightLaw ν).real (fillEvent θstar i) = ratio f (i + 1))
    (hA1 : ∃ Cb : ℝ, ∀ i, 1 ≤ i → i ≤ k + 1 → ∀ᵐ t ∂(ν i), t < Cb)
    (hA2 : ∀ R > 0, ∃ δ > 0, ∀ i, 1 ≤ i → i ≤ k → ∀ t : ℝ, |t - θstar i| ≤ R →
      δ * (t - θstar i) ^ 2 ≤ (t - θstar i) * meanAdj f ν (Function.update θstar i t) i)
    (hA3 : ∃ L : ℝ, ∀ i, 1 ≤ i → i ≤ k → ∀ x y : ℝ,
      |(flightLaw ν).real {z | partialSum z i < x} - (flightLaw ν).real {z | partialSum z i < y}|
        ≤ L * |x - y|) :
    (∀ᵐ ω ∂(pathLaw ν),
        Tendsto (fun n => iterate f k (stepSize A B) θ₁ ω n 1) atTop (𝓝 (θstar 1))) ∧
    (∃ β > 0, ∃ C : ℝ, ∀ n : ℕ,
        Integrable (fun ω => (iterate f k (stepSize A B) θ₁ ω n 1 - θstar 1) ^ 2) (pathLaw ν) ∧
        ∫ ω, (iterate f k (stepSize A B) θ₁ ω n 1 - θstar 1) ^ 2 ∂(pathLaw ν)
          ≤ C * stepSize A B (n + 1) ^ β) := by sorry

end AdaptiveProtection.Convergence
Source
van Ryzin & McGill, Management Science 46(6), 2000, p. 765, proof of Theorem 1, the case of Fare Class 1 (right column, top)
Human review
  • Endorsed by Shuze Chen · Oct 7, 2026

    Confirmed by the moderator at approval.

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