Finite binary transition law from conditional branch masses
ProvedKServer.binary_kernel_of_atom_balanceconditional-expectationfinite-probabilityk-server
Let be a finite set with real weights , and let partition it into atoms. Let choose a branch, and let be constant on each atom. Suppose that for every atom and any ,
Let when and otherwise. Then every real test function satisfies
For probability weights and , 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 sorrySource
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.