Lemma 2: Poisson deviation bounds
ProvedBesbesZeevi.SingleParam.lemma2concentrationp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1poisson-process
Let . There is a constant such that for every , every and every , with
a Poisson random variable with mean satisfies
This is the concentration estimate used to control every demand estimate of the algorithm.
Formalization Note The law of is Mathlib's poissonMeasure with mean . The constant depends only on and is uniform over and over .
Preamble
import Mathlib open MeasureTheory ProbabilityTheory
Formal statement
namespace BesbesZeevi.SingleParam
/-- Lemma 2 (Besbes–Zeevi 2009, p. 27): Poisson deviation bounds. For `μ ∈ [0, M]`,
`r ≥ n^β` and `ε_n = 2 η^{1/2} M^{1/2} (log n)^{1/2} r^{-1/2}`, a Poisson variable `Z` with mean
`μ r` (the law of `N(μ r)`) satisfies `P(Z - μ r > r ε_n) ≤ C/n^η` and
`P(Z - μ r < -r ε_n) ≤ C/n^η` for all `n ≥ 1`, with `C` depending only on `M, η, β`. -/
theorem lemma2 (M η β : ℝ) (hM : 0 < M) (hη : 0 < η) (hβ : 0 < β) :
∃ C : ℝ, 0 < C ∧ ∀ n : ℕ, 1 ≤ n → ∀ μ ∈ Set.Icc (0 : ℝ) M, ∀ r : ℝ, (n : ℝ) ^ β ≤ r →
(poissonMeasure (μ * r).toNNReal
{k : ℕ | (k : ℝ) - μ * r >
r * (2 * Real.sqrt η * Real.sqrt M * Real.sqrt (Real.log n) / Real.sqrt r)}).toReal
≤ C / (n : ℝ) ^ η ∧
(poissonMeasure (μ * r).toNNReal
{k : ℕ | (k : ℝ) - μ * r <
-(r * (2 * Real.sqrt η * Real.sqrt M * Real.sqrt (Real.log n) / Real.sqrt r))}).toReal
≤ C / (n : ℝ) ^ η := by sorry
end BesbesZeevi.SingleParam
Source
Besbes & Zeevi, Dynamic Pricing Without Knowing the Demand Function: Risk Bounds and Near-Optimal Algorithms, Operations Research 57(6), 2009, DOI 10.1287/opre.1080.0640 (authors' final manuscript, last revised December 16, 2007), p. 27 (PDF p. 29), Lemma 2
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.