Theorem 7.1.2 — P(L_N ≥ M+u) ≤ 2exp(−u²/(4(M+u))) and P(L_N ≤ M−u) ≤ 2exp(−u²/(4M))
ProvedTalagrandConc.Subsequences.lis_concentrationLet be independent random variables on , uniformly distributed or, more generally, distributed according to a common non-atomic probability . Let be the length of the longest increasing subsequence of (the largest with and ), and let be a median of . Then for all ,
Since is distributed like the longest increasing subsequence of a uniform random permutation and grows like , these bounds show that fluctuates around its median on the scale , sharper than the scale given by martingale methods.
Formalization Note The variables are the coordinates of under , where is any probability measure on with for every (this includes Lebesgue measure). When (only possible for ) Lean's division gives , so (7.1.4) reads ; the event is empty, so nothing is lost.
Retired 2026-10-27: a Lean-vs-paper fidelity audit found this statement weaker than, or narrower than, the cited result. A corrected statement will be resubmitted.
import Mathlib import Definitions.Def_TalagrandConc_ConvexHull_Basic import Definitions.Def_TalagrandConc_Subsequences_Basic open MeasureTheory open scoped ENNReal
namespace TalagrandConc.Subsequences
/-- Talagrand (1995), Theorem 7.1.2, p. 153. Let `X_1, …, X_N` be i.i.d. on `[0,1]` with a
non-atomic law `μ` (e.g. uniform), realised as the coordinates of `[0,1]^N` under
`P = μ^{⊗N}`, and let `M` be a median of `L_N`. For all `u > 0`,
(7.1.3) `P(L_N ≥ M + u) ≤ 2 exp(−u² / (4(M + u)))` and
(7.1.4) `P(L_N ≤ M − u) ≤ 2 exp(−u² / (4M))`. -/
theorem lis_concentration {N : ℕ} (μ : Measure unitInterval) [IsProbabilityMeasure μ]
(hμ : ∀ t : unitInterval, μ {t} = 0) (M : ℝ)
(hM : TalagrandConc.BinPacking.IsMedian (Measure.pi fun _ : Fin N => μ) (fun x => (lis x : ℝ)) M)
(u : ℝ) (hu : 0 < u) :
(Measure.pi fun _ : Fin N => μ) {x | M + u ≤ (lis x : ℝ)} ≤
ENNReal.ofReal (2 * Real.exp (-(u ^ 2 / (4 * (M + u))))) ∧
(Measure.pi fun _ : Fin N => μ) {x | (lis x : ℝ) ≤ M - u} ≤
ENNReal.ofReal (2 * Real.exp (-(u ^ 2 / (4 * M)))) := by sorry
end TalagrandConc.Subsequences
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.