Proof of Lemma 4, p. ec15 — if Σ L_k = 1 then √(T Σ L_k²) ≥ √T √(K(1/K)²) = √(T/K), with equality iff L_k = 1/K
ProvedPigeonholeDesign.Lower.jensen_displayinequalitiesjensen-inequalitylower-boundp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let , let be real numbers with , and let be a natural number. Then
and, when , the inequality is an equality if and only if for every .
The inequality is Jensen's inequality for the convex function . In the proof of Lemma 4 it bounds the cell-length factor of a partition of into intervals from below by , uniformly over the partition.
Formalization Note In the paper the are the cell lengths; the statement holds for any reals summing to . The equality clause needs (at both sides vanish).
Preamble
import Mathlib import Definitions.Def_PigeonholeDesign_Lower_Setting
Formal statement
namespace PigeonholeDesign.Lower
theorem jensen_display {K : ℕ} (hK : 1 ≤ K) (L : Fin K → ℝ) (hsum : ∑ k, L k = 1) (T : ℕ) :
Real.sqrt T * Real.sqrt (K * (1 / (K : ℝ)) ^ 2) ≤ Real.sqrt (T * ∑ k, L k ^ 2) ∧
Real.sqrt T * Real.sqrt (K * (1 / (K : ℝ)) ^ 2) = Real.sqrt (T / K) ∧
(0 < T → (Real.sqrt (T * ∑ k, L k ^ 2) = Real.sqrt (T / K) ↔ ∀ k, L k = 1 / K)) := by sorry
end PigeonholeDesign.Lower
Source
Zhao and Zhou, Pigeonhole Design: Balancing Sequential Experiments from an Online Matching Perspective, arXiv:2201.12936v6, p. ec15, proof of Lemma 4 (Jensen display)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.