Lemma 6 — P[X_t(S)·1^τ > S | X₁ = x₁] ≤ F(x₁·1^τ − S)^{t−τ}
ProvedAdaptiveBaseStock.Regret.position_tailinventorymarkov-chainp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Consider the lost-sales system with lead time and i.i.d. continuous demand of infinite support, operated under the order-up-to- policy with from an initial inventory vector . Then for every period ,
The inventory position can exceed only while the initial excess has not been consumed, so this bounds the transient phase of the chain; together with the coalescence bound it yields the ergodicity rate of Theorem 3.
Formalization Note The conditioning on is a deterministic start. Lean period is the paper's period , so the paper's reads and the exponent reads . Only the infinite-support case of the paper's lemma is stated.
Preamble
import Mathlib import Definitions.Def_AdaptiveBaseStock_Regret_Model
Formal statement
namespace AdaptiveBaseStock.Regret
open MeasureTheory ProbabilityTheory
/-- Lemma 6 (infinite-support case), p. 16: under the order-up-to-`S` policy started from
`x₁ ∈ ℝ^τ_+`, `P[X_t(S) · 1^τ > S] ≤ F(x₁ · 1^τ - S)^{t-τ}` for every period `t ≥ τ`. Lean period
`t` is the paper's period `t + 1`, so the paper's `t ≥ τ` reads `τ ≤ t + 1` and its exponent
`t - τ` reads `t + 1 - τ`. -/
theorem position_tail {Ω : Type*} [MeasurableSpace Ω] (P : Measure Ω) [IsProbabilityMeasure P]
(D : ℕ → Ω → ℝ) (hD : IsDemandModel P D) (hinf : HasInfiniteSupport P (D 0))
(τ : ℕ) (hτ : 1 ≤ τ) (S : ℝ) (hS : 0 ≤ S) (x₁ : InvVec τ) (hx₁ : IsNonneg x₁)
(t : ℕ) (ht : τ ≤ t + 1) :
P.real {ω | S < position (run (fun _ => S) x₁ (fun n => D n ω) t)}
≤ demandCdf P (D 0) (position x₁ - S) ^ (t + 1 - τ) := by sorry
end AdaptiveBaseStock.Regret
Source
Huh, Janakiraman, Muckstadt, Rusmevichientong, An Adaptive Algorithm for Finding the Optimal Base-Stock Policy in Lost Sales Inventory Systems with Censored Demand, working paper, February 8, 2007 (published version: Math. Oper. Res., 2009, DOI 10.1287/moor.1080.0367), Lemma 6 (first case), p. 16
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.