Theorem 11.2.2 — Gaussian concentration of regular geometric functionals
ProvedTalagrandConc.TSP.gaussian_concentrationFix a regularity constant . There is a constant , depending on but independent of the sample size and the functional, with the following property. Let be independent uniform points in , , and let be a measurable real-valued functional of their set of distinct locations. Suppose that for every dyadic square of side , , finite , and finite , if a point of is within distance of , then
If is any median of , then for every ,
This gives dimension-free fluctuation control for the Euclidean traveling salesman tour length, which satisfies the stated regularity condition, and for other functionals with the same condition.
Formalization Note The event is measured in the product of uniform laws on the square. The statement explicitly requires measurability of the sample functional, following the paper's convention. It quantifies the constant before and .
import Mathlib import Definitions.Def_TalagrandConc_TSP_Basic
namespace TalagrandConc.TSP
open MeasureTheory
/-- Talagrand (1995), Theorem 11.2.2, p. 175. The constant is uniform in
the sample size and the functional, for each fixed regularity constant. -/
theorem gaussian_concentration (K₀ : ℝ) (hK₀ : 0 < K₀) :
∃ K : ℝ, 0 < K ∧ ∀ (N : ℕ) (_ : 0 < N) (L : Finset Point → ℝ),
Regular K₀ L → Measurable (fun x : Fin N → Point => L (sampleSet x)) →
∀ (M : ℝ), IsMedian (N := N) L M → ∀ (t : ℝ), 0 ≤ t →
sampleLaw N {x | t ≤ |L (sampleSet x) - M|} ≤
ENNReal.ofReal (K * Real.exp (-(t ^ 2) / K)) := by sorry
end TalagrandConc.TSP
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.