Theorem 1, p. 765 — under A1, A2 (windowed) and A3, θ^n_i → θ*_i a.s., p_i(θ*) = θ*_i, and E|θ^n_i − θ*_i|² ≤ Cγ_n^{β/2^{i−1}}
DisprovedAdaptiveProtection.Convergence.theorem1_convergenceConsider a single flight leg with fare classes, fares and discount ratios . The class demands of a flight are independent, nonnegative, and have continuous distributions; successive flights are independent and identically distributed. Let satisfy the optimality condition (3), for , where is the fill event (2). Let be generated by the recursion (4),
from an arbitrary initial vector , with step sizes , , . Assume
- A1 each has bounded support: for some constant ;
- A2 (windowed) for every there is such that, for and every with ,
where ; 3. A3 the distributions of the partial sums are Lipschitz: for some , all and all , .
Then for ,
where ; and there are and such that for and all , is integrable and
The theorem says that updating the protection levels from fill events alone, with no demand forecast and no optimization, recovers the optimal nested protection levels, which are moreover ordered.
Formalization Note As printed, A2 asks for one valid for all ; since this cannot hold for , so no instance satisfies it and the printed theorem is vacuous. A2 is pinned to bounded windows with a per window, which is what the proof uses (the iterates stay bounded by Lemma 3) and what the paper's sufficient condition (a density bounded below near ) gives. Continuity of the demand laws is stated as "every singleton is null". Lean's iterate … n is the paper's , so (10) pairs it with stepSize A B (n + 1), i.e. . Integrability is part of the conclusion, so the bound cannot hold through Lean's convention that a non-integrable function has integral .
import Mathlib import Definitions.Def_NestedSeatAlloc_ProbCond_Model import Definitions.Def_AdaptiveProtection_Convergence_Setting open MeasureTheory Filter Topology
namespace AdaptiveProtection.Convergence
/-- Theorem 1 (van Ryzin–McGill 2000, p. 765), with Assumption A2 pinned to bounded windows
(as printed, A2 is unsatisfiable). Lean's `iterate … n` is the paper's `θ^{n+1}`, so the rate (10)
pairs it with `stepSize A B (n + 1) = γ_{n+1}`. -/
theorem theorem1_convergence
(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|) :
(∀ i, 1 ≤ i → i ≤ k → ∀ᵐ ω ∂(pathLaw ν),
Tendsto (fun n => iterate f k (stepSize A B) θ₁ ω n i) atTop (𝓝 (θstar i))) ∧
(∀ i, 1 ≤ i → i ≤ k → interim θstar i = θstar i) ∧
(∃ β > 0, ∃ C : ℝ, ∀ i, 1 ≤ i → i ≤ k → ∀ n : ℕ,
Integrable (fun ω => (iterate f k (stepSize A B) θ₁ ω n i - θstar i) ^ 2) (pathLaw ν) ∧
∫ ω, (iterate f k (stepSize A B) θ₁ ω n i - θstar i) ^ 2 ∂(pathLaw ν)
≤ C * stepSize A B (n + 1) ^ (β / 2 ^ (i - 1))) := by sorry
end AdaptiveProtection.Convergence
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.