Anti-concentration gain of the coin race
ProvedKServer.race_gain_boundThe gain of the coin race. Consider the race of two level chunk systems (alongside head and closing systems) with clamped coins, clamp , sizes bounded by , and both sides carrying a size window below all their chunk sizes. Then the expected imbalance of the consumed side masses satisfies
where and . The imbalance is a bounded-increment martingale up to a drift of at most per step (the clamped coin probabilities equalize the two conditional claims), with per-step conditional variance inside the window; the bound follows from the anti-concentration inequality for discrete martingales with pathwise variance windows. This gain term feeds the expected-total lower bound of the race: it is the mechanism by which the level step gains a -order term over the plain tripling, driving the recursion of the BCR lower bound.
import Mathlib import Definitions.Def_KServer_race_core import Definitions.Def_KServer_race_gain
namespace KServer
open Race
theorem race_gain_bound {X : Type*} [MetricSpace X] {s t : X}
{cB T pe : ℝ} {mL : ℕ}
(A BL BR CC : ChunkSystemB X s t 0 cB T pe mL)
(κ : ℕ) (ε : ℝ) (hε : 0 < ε) (hκL : κ ≤ BL.m) (hκR : κ ≤ BR.m)
(hcB : 0 ≤ cB) {cLo' : ℝ} (hεLo : ε ≤ cLo')
(hLoL : ∀ (l : BL.Ω) (i : Fin BL.m), cLo' ≤ BL.size l i)
(hLoR : ∀ (r : BR.Ω) (i : Fin BR.m), cLo' ≤ BR.size r i) :
Real.sqrt (((κ : ℝ) * cLo' ^ 2) ^ 3
/ (8 * ((κ : ℝ) * (cB + ε) ^ 2) ^ 2
+ 3 * (cB + ε) ^ 2 * ((κ : ℝ) * (cB + ε) ^ 2)))
- (κ : ℝ) * ε
≤ ∑ ω : RΩ A BL BR CC κ, RP A BL BR CC κ ε ω
* |sumL A BL BR CC κ ω - sumR A BL BR CC κ ω| := by sorry
end KServer