Appendix A, Eq. (184) — Cramér-type bound on
ProvedBellWilliams2001.ThresholdPolicy.renewal_lower_deviationlarge-deviationsp2o-batch-pfp1bp2o-gran-per-chapterp2o-plan-paperp2o-v1renewal-process
In the setting of (177)–(179) (as in (181)), let with , put , and let . Then
This is the lower-deviation companion of (181); the second term accounts for the delay , whose law may differ from the others.
Formalization Note The statement is the first member of the chain (184) against its last member. ; takes values in the extended reals.
Preamble
import Mathlib import Definitions.Def_BellWilliams2001_ThresholdPolicy_Paths import Definitions.Def_BellWilliams2001_ThresholdPolicy_LargeDeviation open MeasureTheory ProbabilityTheory open scoped ENNReal
Formal statement
namespace BellWilliams2001.ThresholdPolicy
/-- Appendix A, (184) (p. 645), first member against last member: a Cramér-type lower-deviation
bound for a delayed renewal process. Setting of (177)–(179) as in `renewal_upper_deviation`.
For `ε > 0` with `χ = ν − ε > 0`, `δ = ε/(2ν)` and `t ≥ 0`,
`P(N(t) < χt) ≤ exp(−χ t Λ*((1/ν)(1 + ε/(2(ν − ε))))) + P(ζ(1) > δ t)`. -/
theorem renewal_lower_deviation {Ω : Type*} [MeasurableSpace Ω] (P : Measure Ω)
[IsProbabilityMeasure P] (ζ : ℕ → Ω → ℝ)
(hmeas : ∀ i, Measurable (ζ i))
(hpos : ∀ i ω, 1 ≤ i → 0 < ζ i ω)
(hindep : iIndepFun (fun i : ℕ => ζ (i + 1)) P)
(hident : ∀ i, 2 ≤ i → IdentDistrib (ζ i) (ζ 2) P P)
(hmgf : ∃ δ : ℝ, 0 < δ ∧ ∀ l ∈ Set.Ioo (-δ) δ, ∀ i, 2 ≤ i →
Integrable (fun ω => Real.exp (l * ζ i ω)) P)
(ν : ℝ) (hν : ν = 1 / ∫ ω, ζ 2 ω ∂P)
(ε : ℝ) (hε : 0 < ε) (χ : ℝ) (hχ : χ = ν - ε) (hχpos : 0 < χ)
(δ : ℝ) (hδ : δ = ε / (2 * ν)) (t : ℝ) (ht : 0 ≤ t) :
P {ω | (renewalCount (partialSum (fun i => ζ i ω)) t : ℝ≥0∞) < ENNReal.ofReal (χ * t)} ≤
EReal.exp (-(((χ * t : ℝ) : EReal) *
legendre (logMGF P (ζ 2)) ((1 / ν) * (1 + ε / (2 * (ν - ε)))))) +
P {ω | δ * t < ζ 1 ω} := by sorry
end BellWilliams2001.ThresholdPolicy
Source
Bell and Williams, Dynamic scheduling of a system with two parallel servers in heavy traffic with resource pooling, Ann. Appl. Probab. 11 (2001), p. 645, Appendix A, (184)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.