Theorem 6.5 — P(|B_N − M| ≥ 1 + u) ≤ 8 exp(−u²/(64 N E X₁²)) for 0 ≤ u ≤ 8√2 N E X₁²
ProvedTalagrandConc.BinPacking.theorem_6_5bin-packingconcentration-of-measurep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-bookp2o-v1probability
Let be independent items with common law on , realised as the coordinates of under the product probability , and let be the minimum number of unit bins into which they can be packed. Write , and let be any median of , i.e. and . Then for all with ,
The variance proxy in the exponent is rather than , which is the scale one expects when items are small, and improves on the martingale bound .
Formalization Note The paper writes "for all "; the restriction is implicit (its proof sets with ) and is stated explicitly. When the range forces , and Lean's convention makes the bound .
Preamble
import Mathlib import Definitions.Def_TalagrandConc_BinPacking_Basic
Formal statement
namespace TalagrandConc.BinPacking
open MeasureTheory
/-- Talagrand (1995), p. 152, Theorem 6.5: if `M` is a median of `B_N` under the product
probability `P = μ^{⊗N}` on `[0,1]^N`, then for all `0 ≤ u ≤ 8 √2 N E X₁²`,
`P(|B_N(X₁, …, X_N) − M| ≥ 1 + u) ≤ 8 exp(−u² / (64 N E X₁²))`.
(The paper writes "for all `u ≤ 8√2 N E X₁²`"; `u ≥ 0` is implicit — its proof sets
`u = 4t √N (E X₁²)^{1/2}` with `t > 0` — and is stated here.) -/
theorem theorem_6_5 (μ : Measure unitInterval) [IsProbabilityMeasure μ] (N : ℕ) (M : ℝ)
(hM : IsMedian (Measure.pi (fun _ : Fin N => μ)) (fun x => (binNumber x : ℝ)) M)
(u : ℝ) (hu0 : 0 ≤ u) (hu : u ≤ 8 * Real.sqrt 2 * N * secondMoment μ) :
Measure.pi (fun _ : Fin N => μ) {x | 1 + u ≤ |(binNumber x : ℝ) - M|} ≤
ENNReal.ofReal (8 * Real.exp (-(u ^ 2 / (64 * N * secondMoment μ)))) := by sorry
end TalagrandConc.BinPacking
Source
Talagrand, Concentration of measure and isoperimetric inequalities in product spaces, Publ. Math. IHÉS 81 (1995), p. 152, Theorem 6.5
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.