Lemma 8 — concentration of the multinomial distribution
ProvedLPResolvingRM.lemma_8linear-programmingonline-linear-programmingp2o-gran-per-chapterp2o-plan-paperp2o-v1regret-analysisrevenue-management
Let . For , and (the empirical frequencies of i.i.d. draws from ),
The analysis applies it to the frequencies used by the sampled LP.
Formalization Note The constant is on the rendered page (the text layer flattens it to "2d").
Differences from the source:
- encoding: q̂ ∼ (1/t)·Mul(t, q) → the empirical frequencies #{s : ω_s = j}/t of t i.i.d. draws, the probability being the finite sum of ∏s q{ω_s} over the draws in the event; reason: the same law
- encoding: t implicit (it divides) → t ≥ 1; reason: (1/t)·Mul(t, q) presupposes t ≥ 1
Preamble
import Mathlib open scoped Classical
Formal statement
namespace LPResolvingRM
/-- **Lemma 8 (ℓ₁ concentration of the multinomial distribution)** (arXiv:2101.11092v3, p.22,
citing Jaksch et al. 2010, App. C.1): for `q ∈ Ξ_d = {q ∈ ℝ^d | ∑_j q_j = 1, 0 < q_j < 1}` and
`q̂ ∼ (1/t)·Mul(t, q)`,
`P(‖q̂ − q‖₁ ≥ ϵ) ≤ 2^d exp(−tϵ²/2)` for any `ϵ > 0`.
**Formalization Note.** `q̂` is the vector of empirical frequencies `#{s : ω_s = j}/t` of `t`
i.i.d. draws `ω_1, …, ω_t` from `q` on `Fin d` (the law `(1/t)·Mul(t, q)`), and the probability is
the finite sum of `∏_s q_{ω_s}` over the draws in the event. `t ≥ 1` (it divides). The constant
is `2^d` (rendered page; the text layer flattens it to "2d"). -/
theorem lemma_8 {d : ℕ} (q : Fin d → ℝ) (hq_sum : ∑ j, q j = 1) (hq : ∀ j, 0 < q j ∧ q j < 1)
(t : ℕ) (ht : 0 < t) (ε : ℝ) (hε : 0 < ε) :
∑ ω : Fin t → Fin d, (∏ s, q (ω s)) *
(if ε ≤ ∑ j, |((Finset.univ.filter fun s => ω s = j).card : ℝ) / t - q j| then 1 else 0)
≤ 2 ^ d * Real.exp (-(t * ε ^ 2 / 2)) := by sorry
end LPResolvingRM
Source
Chen, Li, Ye, An Improved Analysis of LP-based Control for Revenue Management, arXiv:2101.11092v3, Lemma 8, p.22 (citing Jaksch et al. 2010, App. C.1)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.