Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Exact second and fourth moment identities for a balanced race

Proved
KServer.race_kernel_moments

by kwal0203 · Oct 30, 2026 · Mathlib c5ea003 (Lean v4.30.0)

k-servermartingalesmoment-identity

Let Ω\OmegaΩ be a finite set, let PωP_\omegaPω​ be real weights, and let Sj,Lj,RjS_j,L_j,R_jSj​,Lj​,Rj​ be real-valued arrays for 0≤j≤n0\le j\le n0≤j≤n. Suppose S0=0S_0=0S0​=0, every denominator Lj+RjL_j+R_jLj​+Rj​ is nonzero for j<nj<nj<n, and for every real test function fff the averaged transition identity holds:

∑ωPωf(Sj+1)=∑ωPω[RjLj+Rjf(Sj+Lj)+LjLj+Rjf(Sj−Rj)].\sum_\omega P_\omega f(S_{j+1})=\sum_\omega P_\omega\left[\frac{R_j}{L_j+R_j}f(S_j+L_j)+\frac{L_j}{L_j+R_j}f(S_j-R_j)\right].ω∑​Pω​f(Sj+1​)=ω∑​Pω​[Lj​+Rj​Rj​​f(Sj​+Lj​)+Lj​+Rj​Lj​​f(Sj​−Rj​)].

Then the terminal second and fourth moments satisfy the exact identities

∑ωPωSn2=∑j<n∑ωPωLjRj,\sum_\omega P_\omega S_n^2=\sum_{j<n}\sum_\omega P_\omega L_jR_j,ω∑​Pω​Sn2​=j<n∑​ω∑​Pω​Lj​Rj​, ∑ωPωSn4=∑j<n∑ωPωLjRj(6Sj2+4Sj(Lj−Rj)+Lj2−LjRj+Rj2).\sum_\omega P_\omega S_n^4=\sum_{j<n}\sum_\omega P_\omega L_jR_j\left(6S_j^2+4S_j(L_j-R_j)+L_j^2-L_jR_j+R_j^2\right).ω∑​Pω​Sn4​=j<n∑​ω∑​Pω​Lj​Rj​(6Sj2​+4Sj​(Lj​−Rj​)+Lj2​−Lj​Rj​+Rj2​).

Every term inside a weighted sum is evaluated at the same outcome ω\omegaω. These formulas turn terminal-moment conditions into sums of local race quantities. When the weights are probabilities and the two step sizes are nonnegative, the transition is the balanced left/right race used by BCR. The fourth-moment formula retains the asymmetric cubic contribution.

Formalization Note The theorem is algebraic: it does not need positivity or normalization of the weights, or positivity of the step sizes. It includes n=0n=0n=0. The averaged transition identity is the exact hypothesis; no stronger filtration-adaptedness claim is implicit.

Preamble
import Mathlib.Algebra.BigOperators.Group.Finset.Basic
import Mathlib.Data.Real.Basic
import Mathlib.Tactic.FieldSimp
import Mathlib.Tactic.Ring

set_option autoImplicit false
open scoped BigOperators
Formal statement
theorem KServer.race_kernel_moments {Ω : Type*} [Fintype Ω] (P : Ω → ℝ)
    (S L R : ℕ → Ω → ℝ) (n : ℕ) (hzero : ∀ ω, S 0 ω = 0)
    (hden : ∀ j < n, ∀ ω, L j ω + R j ω ≠ 0)
    (hstep : ∀ j < n, ∀ f : ℝ → ℝ,
      (∑ ω, P ω * f (S (j + 1) ω)) =
        ∑ ω, P ω * (R j ω / (L j ω + R j ω) * f (S j ω + L j ω) +
          L j ω / (L j ω + R j ω) * f (S j ω - R j ω))) :
    (∑ ω, P ω * S n ω ^ 2) = ∑ j ∈ Finset.range n, ∑ ω, P ω * (L j ω * R j ω) ∧
    (∑ ω, P ω * S n ω ^ 4) = ∑ j ∈ Finset.range n, ∑ ω,
      P ω * (L j ω * R j ω * (6 * S j ω ^ 2 + 4 * S j ω * (L j ω - R j ω) +
        L j ω ^ 2 - L j ω * R j ω + R j ω ^ 2)) := by sorry
Source
S. Bubeck, C. Coester, Y. Rabani, The Randomized k-Server Conjecture Is False!, https://arxiv.org/html/2211.05753v2, Section 4.1, stage 2a (transition probabilities), and Section 4.2, equations (3) and (4), printed pp. 16–19. Second identity: elementary fourth-power expansion of the same transition kernel, proved here; the paper states the conditional second moment in equation (4).

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