Lemma 2: Poisson deviation bound
ProvedBesbesZeevi.Nonparametric.lemma2_poisson_deviationconcentrationp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1poisson-distributionprobability
Let . There is a constant , depending only on , with the following property.
Let be any sequence with for all , and let . Put
and let be a Poisson random variable with mean . Then for all ,
This bound controls the demand estimates of the learning phase.
Formalization Note is represented by its law, Mathlib's poissonMeasure with mean . The constant is quantified before the sequence and before : it is uniform in them, as the paper's proof shows and as the later lemmas use it.
Preamble
import Mathlib open MeasureTheory ProbabilityTheory
Formal statement
namespace BesbesZeevi.Nonparametric
/-- Lemma 2, p. 27: for `μ ∈ [0, M]`, `r_n ≥ n^β` (`β > 0`) and
`ε_n = 2 η^{1/2} M^{1/2} (log n)^{1/2} r_n^{-1/2}`, a Poisson variable `N(μ r_n)` with mean `μ r_n`
satisfies `P(N(μ r_n) - μ r_n > r_n ε_n) ≤ C/n^η` and `P(N(μ r_n) - μ r_n < -r_n ε_n) ≤ C/n^η`
for all `n ≥ 1`, with `C` depending only on `M, η, β`. -/
theorem lemma2_poisson_deviation (M η β : ℝ) (hM : 0 < M) (hη : 0 < η) (hβ : 0 < β) :
∃ C : ℝ, 0 < C ∧
∀ r : ℕ → ℝ, (∀ n : ℕ, 1 ≤ n → (n : ℝ) ^ β ≤ r n) →
∀ μ ∈ Set.Icc (0 : ℝ) M, ∀ n : ℕ, 1 ≤ n →
poissonMeasure (Real.toNNReal (μ * r n))
{k : ℕ | (k : ℝ) - μ * r n >
r n * (2 * Real.sqrt η * Real.sqrt M * Real.sqrt (Real.log n) / Real.sqrt (r n))}
≤ ENNReal.ofReal (C / (n : ℝ) ^ η) ∧
poissonMeasure (Real.toNNReal (μ * r n))
{k : ℕ | (k : ℝ) - μ * r n <
-(r n * (2 * Real.sqrt η * Real.sqrt M * Real.sqrt (Real.log n) / Real.sqrt (r n)))}
≤ ENNReal.ofReal (C / (n : ℝ) ^ η) := by sorry
end BesbesZeevi.Nonparametric
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 29), Lemma 2
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.