Theorem 10.5 — concentration of the random assignment cost L_N around its median
ProvedTalagrandConc.Assignment.theorem_10_5assignment-problemconcentration-of-measurep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-bookp2o-v1probability
Let the costs , , , , be independent and uniformly distributed on , and let
be the optimal assignment cost. There is a universal constant such that for every , every median of and every :
Since stays bounded as , this shows that the fluctuations of are at most of order , much smaller than its mean.
Formalization Note One constant serves both (10.7) and (10.8) and is chosen before , and . A median is any with and . The paper leaves implicit; for negative (10.7) would fail. For , , and gives .
Preamble
import Mathlib import Definitions.Def_TalagrandConc_Assignment_Basic
Formal statement
namespace TalagrandConc.Assignment
open MeasureTheory
/-- Talagrand (1995), p. 169, Theorem 10.5. There is a universal constant `K > 0` such that
for every `N ≥ 3`, every median `M` of the optimal assignment cost `L_N` (costs i.i.d.
uniform on `[0, 1]`) and every `t ≥ 0`:
(10.7) if `t ≤ √(log N)` then `P(|L_N − M| ≥ K t (log N)² / (√N log log N)) ≤ 2 exp(−t²)`;
(10.8) if `t ≥ √(log N)` then `P(|L_N − M| ≥ K t³ log N / (√N log t²)) ≤ 2 exp(−t²)`. -/
theorem theorem_10_5 :
∃ K : ℝ, 0 < K ∧ ∀ N : ℕ, 3 ≤ N → ∀ M : ℝ, TalagrandConc.BinPacking.IsMedian (costLaw N) optCost M →
∀ t : ℝ, 0 ≤ t →
(t ≤ Real.sqrt (Real.log N) →
costLaw N {X | K * t * Real.log N ^ 2 / (Real.sqrt N * Real.log (Real.log N)) ≤
|optCost X - M|} ≤ ENNReal.ofReal (2 * Real.exp (-t ^ 2))) ∧
(Real.sqrt (Real.log N) ≤ t →
costLaw N {X | K * t ^ 3 * Real.log N / (Real.sqrt N * Real.log (t ^ 2)) ≤
|optCost X - M|} ≤ ENNReal.ofReal (2 * Real.exp (-t ^ 2))) := by sorry
end TalagrandConc.Assignment
Source
Talagrand, Concentration of measure and isoperimetric inequalities in product spaces, Publ. Math. IHÉS 81 (1995), p. 169, Theorem 10.5, Eqs. (10.7)–(10.8)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.