A finite weighted second–fourth moment lower bound on mean absolute size
ProvedKServer.race_abs_moment_lowerk-servermoment-inequalityprobability
Let be a finite set, let be weights, and let . For , suppose
Then
The weights need not sum to one. This quantitative moment estimate supplies an absolute-imbalance gain in the BCR race accounting, and also applies to any finite weighted statistic with the stated moment bounds.
Formalization Note The constants are deliberately loose; this is an elementary sufficient inequality, not the central-limit theorem used in the source paper.
Preamble
import Mathlib open scoped BigOperators
Formal statement
theorem KServer.race_abs_moment_lower {Ω : Type*} [Fintype Ω] (P : Ω → ℝ) (Z : Ω → ℝ)
(hP : ∀ ω, 0 ≤ P ω) (s : ℝ) (hs : 0 < s)
(hsecond : s ^ 2 / 4 ≤ ∑ ω, P ω * Z ω ^ 2)
(hfourth : (∑ ω, P ω * Z ω ^ 4) ≤ 4 * s ^ 4) :
s / 50 ≤ ∑ ω, P ω * |Z ω| := by sorrySource
Bubeck, Coester and Rabani, The Randomized k-Server Conjecture Is False!, https://arxiv.org/html/2211.05753v2, Section 4.1 (stages 1–3), Section 4.2, equations (3) and (4), printed pp. 16–19. Original elementary moment inequality for the absolute-imbalance term in equation (3); the displayed constants are derived here and are not quoted from the paper.