Lemma 14, p. 41 — Bernstein bound for the sum of [0,1]-valued variables over a Bernoulli(p_O) sample Ω
ProvedInventoryAnomaly.EW.lemma_14bernsteinconcentrationp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1random-sampling
Let , , be i.i.d. variables, , and let be independent random variables with . Put . There is a universal constant such that, with probability at least ,
This concentration inequality is used to control (with ) and the empirical CDF counts in the analysis of the moment-matching estimator.
Formalization Note. is written . The family is assumed jointly independent (the proof uses independence of the products ). Only the first display of the lemma is formalized; its "in particular" clause hides an unnamed threshold . .
Preamble
import Mathlib open MeasureTheory ProbabilityTheory open scoped NNReal
Formal statement
namespace InventoryAnomaly.EW
theorem lemma_14 : ∃ C : ℝ, 0 < C ∧
∀ {Ω : Type} [MeasurableSpace Ω] (P : Measure Ω) [IsProbabilityMeasure P] {n m : ℕ}
(pO : ℝ) (O T : Fin n × Fin m → Ω → ℝ) (p : Fin n × Fin m → ℝ),
0 < n → 0 < m → 0 ≤ pO → pO ≤ 1 →
(∀ ij, Measurable (O ij)) → (∀ ij, Measurable (T ij)) →
iIndepFun (fun k : (Fin n × Fin m) ⊕ (Fin n × Fin m) => Sum.elim O T k) P →
(∀ ij ω, O ij ω = 0 ∨ O ij ω = 1) → (∀ ij, P.real {ω | O ij ω = 1} = pO) →
(∀ ij ω, 0 ≤ T ij ω ∧ T ij ω ≤ 1) → (∀ ij, ∫ ω, T ij ω ∂P = p ij) →
1 - 1 / ((n : ℝ) * m) ≤ P.real {ω | |∑ ij, O ij ω * T ij ω - ∑ ij, pO * p ij| ≤
C * (Real.sqrt ((∑ ij, pO * p ij) * Real.log (m * n)) + Real.log (m * n))} := by sorry
end InventoryAnomaly.EW
Source
Farias, Li & Peng, Fixing Inventory Inaccuracies at Scale, arXiv:2006.13126v3, p. 41, Lemma 14
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.