Lemma 4, p. 37 — Poisson tail bound for
ProvedResolvingNRM.IRT.poisson_tail_boundconcentrationp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1poisson
Let be a Poisson random variable with parameter . For every with ,
This is the concentration inequality the paper uses (in Lemma 6) to show that the acceptance counts of the first epoch of IRT stay close to their means with overwhelming probability.
Formalization Note The hypothesis is added. The paper states the bound for every , which is false: for , one has . Every use of the lemma in the paper is in the range . The probability is written as the sum of the Poisson masses over the with .
Preamble
import Mathlib import Definitions.Def_RLPBidPrice_Unbiased_Model import Definitions.Def_ResolvingNRM_IRT_Model open RLPBidPrice.Unbiased Matrix
Formal statement
namespace ResolvingNRM.IRT
theorem poisson_tail_bound (μ x : ℝ) (hμ : 0 < μ) (hx : 0 < x) (hxμ : x ≤ μ) :
∑' k : ℕ, (if x ≤ |(k : ℝ) - μ| then poissonPMF μ k else 0) ≤
2 * Real.exp (-(x ^ 2) / (3 * μ)) := by sorry
end ResolvingNRM.IRT
Source
Bumpensanti, Wang, A Re-solving Heuristic with Uniformly Bounded Loss for Network Revenue Management, arXiv:1802.06192v3, Lemma 4 (Poisson Tail Bound, Pollard (2015)), p. 37
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.