Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 13.4 — P(∥∑iεiXi∥≥2aq+3t+u)≤2q+1qk+1+4e−u2/32qs2+2P(∑i≤k∥Xi∥∗>t)P(\|\sum_i\varepsilon_iX_i\|\ge 2aq+3t+u)\le \frac{2^{q+1}}{q^{k+1}}+4e^{-u^2/32qs^2}+2P(\sum_{i\le k}\|X_i\|^*>t)P(∥∑i​εi​Xi​∥≥2aq+3t+u)≤qk+12q+1​+4e−u2/32qs2+2P(∑i≤k​∥Xi​∥∗>t)

Proved
TalagrandConc.BanachSums.thm_13_4

by mikedeng1 · Oct 6, 2026 · Mathlib 0df444a (Lean v4.33.1)

banach-spacesconcentration-of-measurep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-bookp2o-v1probability

Let WWW be a real Banach space with its Borel σ\sigmaσ-algebra, X1,…,XNX_1,\dots,X_NX1​,…,XN​ independent WWW-valued random variables (not necessarily identically distributed) with laws μ1,…,μN\mu_1,\dots,\mu_Nμ1​,…,μN​, and ε1,…,εN\varepsilon_1,\dots,\varepsilon_Nε1​,…,εN​ independent uniform random signs, independent of (Xi)(X_i)(Xi​). Write EEE and PPP for expectation and probability under the joint law. Set

a=2E∥∑i≤NεiXi∥,s2=Esup⁡{∑i≤Nw∗(Xi)2: w∗∈W∗, ∥w∗∥≤1},a=2E\Big\|\sum_{i\le N}\varepsilon_iX_i\Big\|,\qquad s^2=E\sup\Big\{\sum_{i\le N}w^*(X_i)^2:\ w^*\in W^*,\ \|w^*\|\le1\Big\},a=2E​i≤N∑​εi​Xi​​,s2=Esup{i≤N∑​w∗(Xi​)2: w∗∈W∗, ∥w∗∥≤1},

and let ∥Xi∥∗\|X_i\|^*∥Xi​∥∗ be the iii-th largest of ∥X1∥,…,∥XN∥\|X_1\|,\dots,\|X_N\|∥X1​∥,…,∥XN​∥. Assume the maps x↦∥∑iεixi∥x\mapsto\|\sum_i\varepsilon_ix_i\|x↦∥∑i​εi​xi​∥ (each sign pattern) and x↦sup⁡∥w∗∥≤1∑iw∗(xi)2x\mapsto\sup_{\|w^*\|\le1}\sum_iw^*(x_i)^2x↦sup∥w∗∥≤1​∑i​w∗(xi​)2 on WNW^NWN are measurable.

Then for all integers q≥2q\ge2q≥2, k≥0k\ge0k≥0 and all u,t>0u,t>0u,t>0,

P(∥∑i≤NεiXi∥≥2aq+3t+u)≤2q+1qk+1+4exp⁡(−u232qs2)+2P(∑i≤k∥Xi∥∗>t).P\Big(\Big\|\sum_{i\le N}\varepsilon_iX_i\Big\|\ge 2aq+3t+u\Big)\le\frac{2^{q+1}}{q^{k+1}}+4\exp\Big(-\frac{u^2}{32qs^2}\Big)+2P\Big(\sum_{i\le k}\|X_i\|^*>t\Big).P(​i≤N∑​εi​Xi​​≥2aq+3t+u)≤qk+12q+1​+4exp(−32qs2u2​)+2P(i≤k∑​∥Xi​∥∗>t).

The bound controls the tail of a Rademacher sum of independent Banach-space-valued variables using only its mean, the weak variance s2s^2s2, and the distribution of the kkk largest summands, with no integrability assumption beyond these quantities; it is the isoperimetric replacement for martingale bounds in laws of large numbers and of the iterated logarithm in Banach spaces.

Formalization Note The variables are realized canonically: the joint law is (Measure.pi μ).prod (Komlos.spMeasure N) on WN×{true,false}NW^N\times\{\text{true},\text{false}\}^NWN×{true,false}N. aaa and s2s^2s2 are lower Lebesgue integrals in [0,∞][0,\infty][0,∞], so they need no integrability hypothesis; if a=∞a=\inftya=∞ the event is empty. The term exp⁡(−u2/(32qs2))\exp(-u^2/(32qs^2))exp(−u2/(32qs2)) is computed with s2s^2s2 converted to a real; at s2=0s^2=0s2=0 or s2=∞s^2=\inftys2=∞ this reads as exp⁡(0)=1\exp(0)=1exp(0)=1, so the right-hand side is at least 444 and the inequality is trivially true there (where the paper's expression is undefined, respectively equal to 444). The paper writes q∈Nq\in\mathbf Nq∈N; the hypothesis q≥2q\ge2q≥2 is the range of Theorem 3.1.1 used in the proof, and the bound is trivially true for q∈{0,1}q\in\{0,1\}q∈{0,1}. Measurability hypotheses state the paper's convention of ignoring measurability (pp. 81–82).

Preamble
import Mathlib
import Definitions.Def_Komlos_RandomSignModel
import Definitions.Def_TalagrandConc_BanachSums_Basic

open MeasureTheory
open scoped ENNReal
Formal statement
namespace TalagrandConc.BanachSums

theorem thm_13_4 {W : Type*} [NormedAddCommGroup W] [NormedSpace ℝ W] [CompleteSpace W]
    [MeasurableSpace W] [BorelSpace W] {N : ℕ}
    (μ : Fin N → Measure W) [∀ i, IsProbabilityMeasure (μ i)]
    (hnorm : ∀ ε : Fin N → Bool, Measurable (fun x : Fin N → W => ‖signedSum ε x‖))
    (hσ : Measurable (fun x : Fin N → W => sigmaSq x))
    (q k : ℕ) (hq : 2 ≤ q) (u t : ℝ) (hu : 0 < u) (ht : 0 < t) :
    ((Measure.pi μ).prod (Komlos.spMeasure N))
        {p | 2 * (2 * ∫⁻ p', ENNReal.ofReal ‖signedSum p'.2 p'.1‖
                ∂((Measure.pi μ).prod (Komlos.spMeasure N))) * q
              + ENNReal.ofReal (3 * t + u)
            ≤ ENNReal.ofReal ‖signedSum p.2 p.1‖}
      ≤ 2 ^ (q + 1) / (q : ℝ≥0∞) ^ (k + 1)
        + ENNReal.ofReal (4 * Real.exp (-(u ^ 2 /
            (32 * q * (∫⁻ x, ENNReal.ofReal (sigmaSq x) ∂(Measure.pi μ)).toReal))))
        + 2 * Measure.pi μ {x | t < topSum x k} := by sorry

end TalagrandConc.BanachSums
Source
Talagrand, Concentration of measure and isoperimetric inequalities in product spaces, Publ. Math. IHÉS 81 (1995), p. 200, Theorem 13.4
Human review
  • Endorsed by Shuze Chen · Oct 6, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 6, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me