Lemma 3, p. 12 — Kingman's series for E[I^r_L], E[I^r_∞], and E[I^r∞_∞] − E[I^r∞_L] ≤ ((1−γ)eϑ(L+1))⁻¹γ^{L+1}
ProvedLostSalesExpGap.ConstOrder.lemma_3lost-salesp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1queueingspitzer-identity
Let be i.i.d. nonnegative demands with finite mean and strictly positive variance, , and let , . Let be as in Sec. 2.3. Then:
- for all and ,
- if in addition ,
- for all ,
These are Theorems 1 and 4 of Kingman (1962), specialized to the queue with interarrival law and constant service time .
Formalization Note Item 2 is an identity in (lower integrals and an extended-real series). Item 3 is stated additively in , , with when . Sums are indexed from in Lean: the term at is the paper's term . in items 1 and 3 is any horizon , not tied to the model's lead time; enter only through .
Preamble
import Mathlib import Definitions.Def_LostSalesExpGap_ConstOrder_ConstantOrder open MeasureTheory ProbabilityTheory open scoped ENNReal NNReal BigOperators
Formal statement
namespace LostSalesExpGap.ConstOrder
/-- Lemma 3, p. 12 (Theorems 1 and 4 of Kingman (1962)). For `r ∈ [0, E[D]]` and `m ≥ 1`,
`E[I^r_m] = Σ_{n=1}^m (1/n) E[(n r − Σ_{i=1}^n D_i)^+]`; for `r ∈ [0, E[D])`,
`E[I^r_∞] = Σ_{n=1}^∞ (1/n) E[(n r − Σ_{i=1}^n D_i)^+]`; and
`E[I^{r∞}_∞] − E[I^{r∞}_m] ≤ ((1 − γ) e ϑ (m + 1))⁻¹ γ^{m+1}`. Sums over `n` are shifted by one:
the summand at `n` is the paper's term `n + 1`. -/
theorem lemma_3 (P : CappedBaseStock.DemandLaw) (c : CappedBaseStock.Parameters)
(hP : LostSalesConstantOrder.LargeLeadTime.NonDeterministic P) :
(∀ r : ℝ, 0 ≤ r → r ≤ CappedBaseStock.mean P → ∀ m : ℕ, 1 ≤ m →
EIL P r m = ∑ n ∈ Finset.range m, (1 / ((n : ℝ) + 1)) *
∫ d, max (((n : ℝ) + 1) * r - ∑ i ∈ Finset.range (n + 1), (d i : ℝ)) 0
∂CappedBaseStock.demandPathLaw P) ∧
(∀ r : ℝ, 0 ≤ r → r < CappedBaseStock.mean P →
EIinf P r = ∑' n : ℕ, ENNReal.ofReal (1 / ((n : ℝ) + 1)) *
∫⁻ d, ENNReal.ofReal (((n : ℝ) + 1) * r - ∑ i ∈ Finset.range (n + 1), (d i : ℝ))
∂CappedBaseStock.demandPathLaw P) ∧
(∀ m : ℕ, 1 ≤ m →
EIinf P (rInf P c) ≤ ENNReal.ofReal (EIL P (rInf P c) m) +
ENNReal.ofReal (((1 - gamma P c) * Real.exp 1 * ((m : ℝ) + 1))⁻¹ * varthetaInv P c *
gamma P c ^ (m + 1))) := by sorry
end LostSalesExpGap.ConstOrder
Source
Xin, Goldberg, Optimality gap of constant-order policies decays exponentially in the lead time for lost sales models, arXiv:1409.1499v2, Lemma 3, p. 12
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.