Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Finite binary transition law from conditional branch masses

Proved
KServer.binary_kernel_of_atom_balance

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

conditional-expectationfinite-probabilityk-server

Let Ω\OmegaΩ be a finite set with real weights PωP_\omegaPω​, and let H:Ω→NH:\Omega\to\mathbb NH:Ω→N partition it into atoms. Let B:Ω→{false,true}B:\Omega\to\{\mathrm{false},\mathrm{true}\}B:Ω→{false,true} choose a branch, and let u,v,q:Ω→Ru,v,q:\Omega\to\mathbb Ru,v,q:Ω→R be constant on each atom. Suppose that for every atom AAA and any ω0∈A\omega_0\in Aω0​∈A,

∑ω∈A, B(ω)=truePω=q(ω0)∑ω∈APω.\sum_{\omega\in A,\,B(\omega)=\mathrm{true}}P_\omega=q(\omega_0)\sum_{\omega\in A}P_\omega.ω∈A,B(ω)=true∑​Pω​=q(ω0​)ω∈A∑​Pω​.

Let Y(ω)=u(ω)Y(\omega)=u(\omega)Y(ω)=u(ω) when B(ω)=trueB(\omega)=\mathrm{true}B(ω)=true and Y(ω)=v(ω)Y(\omega)=v(\omega)Y(ω)=v(ω) otherwise. Then every real test function fff satisfies

∑ωPωf(Y(ω))=∑ωPω[q(ω)f(u(ω))+(1−q(ω))f(v(ω))].\sum_\omega P_\omega f(Y(\omega))=\sum_\omega P_\omega\left[q(\omega)f(u(\omega))+(1-q(\omega))f(v(\omega))\right].ω∑​Pω​f(Y(ω))=ω∑​Pω​[q(ω)f(u(ω))+(1−q(ω))f(v(ω))].

For probability weights and 0≤q≤10\le q\le10≤q≤1, the hypothesis specifies the branch probability conditional on the atom. The conclusion is the finite mixture law used to evaluate all moments of the next state.

Formalization Note The identity is algebraic and does not require positive weights, normalized total mass, or positive atom masses. In particular, it involves no division by atom mass.

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

set_option autoImplicit false
open scoped BigOperators
Formal statement
theorem KServer.binary_kernel_of_atom_balance {Ω : Type*} [Fintype Ω] (P : Ω → ℝ) (H : Ω → ℕ)
    (B : Ω → Bool) (u v q : Ω → ℝ)
    (hknown : ∀ ω ω', H ω = H ω' → u ω = u ω' ∧ v ω = v ω' ∧ q ω = q ω')
    (hbalance : ∀ ω₀,
      (∑ ω ∈ Finset.univ.filter (fun ω => H ω = H ω₀ ∧ B ω = true), P ω) =
        q ω₀ * (∑ ω ∈ Finset.univ.filter (fun ω => H ω = H ω₀), P ω)) :
    ∀ f : ℝ → ℝ,
      (∑ ω, P ω * f (if B ω then u ω else v ω)) =
        ∑ ω, P ω * (q ω * f (u ω) + (1 - q ω) * f (v ω)) := 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 (the probabilities p_L and p_R), and Section 4.2, equations (3)–(4), printed pp. 16–19. Elementary finite law of total expectation for the atomwise selection probabilities; the general algebraic formulation is proved here.

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