Sec. 3, p. 13 — Chernoff: ℙ(nr∞ ≥ Σ_{i≤n} D_i) ≤ γ^n
ProvedLostSalesExpGap.ConstOrder.chernoff_stepchernoff-boundlarge-deviationsp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be i.i.d. nonnegative demands with finite mean, let be the best constant order and . Then for every ,
This is the large-deviation estimate that makes the optimality gap decay like .
Formalization Note No positive-variance assumption is needed for this bound.
Preamble
import Mathlib import Definitions.Def_LostSalesExpGap_ConstOrder_ConstantOrder open MeasureTheory ProbabilityTheory open scoped ENNReal NNReal BigOperators
Formal statement
namespace LostSalesExpGap.ConstOrder
/-- Sec. 3, p. 13 (proof of Theorem 1): by Chernoff's inequality,
`ℙ(n r∞ ≥ Σ_{i=1}^n D_i) ≤ γ^n` for every `n ≥ 1`. -/
theorem chernoff_step (P : CappedBaseStock.DemandLaw) (c : CappedBaseStock.Parameters) :
∀ n : ℕ, 1 ≤ n →
CappedBaseStock.demandPathLaw P
{d | ∑ i ∈ Finset.range n, (d i : ℝ) ≤ (n : ℝ) * rInf P c} ≤
ENNReal.ofReal (gamma P c ^ n) := 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, Sec. 3, proof of Theorem 1, p. 13 (Chernoff step)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.