Theorem 2.1 — WM mistake bound from initial and final weights
ProvedWeightedMajority.Basic.theorem_2_1Let WM use any factor and any strictly positive initial weights on a finite pool. On an arbitrary finite sequence of binary predictions and labels, let be the number of mistakes made by the master, and let and be the initial and final total pool weights. Every legal WM run with satisfies
The bound measures the master's mistakes by the decrease in the pool's total weight and applies without a distributional assumption on the sequence.
Formalization Note Both logarithms are natural; their common base cancels, as specified on p. 220. When and , the paper says the logarithmic bound becomes vacuous (infinite). The explicit condition excludes exactly that case while retaining the Halving Algorithm case whenever its final weight is positive.
import Mathlib import Definitions.Def_WeightedMajority_Basic_IsWMRun
namespace WeightedMajority.Basic
/-- Littlestone and Warmuth's Theorem 2.1. -/
theorem theorem_2_1 {n T : ℕ} (β : ℝ) (hβ₀ : 0 ≤ β) (hβ₁ : β < 1)
(initial : Fin n → ℝ) (hinitial : ∀ i, 0 < initial i)
(x : Fin T → Fin n → Bool) (label : Fin T → Bool)
(w : ℕ → Fin n → ℝ) (prediction : Fin T → Bool)
(hrun : IsWMRun β initial x label w prediction)
(hfinal : 0 < totalWeight w T) :
(mistakeCount prediction label : ℝ) ≤
Real.log (totalWeight w 0 / totalWeight w T) /
Real.log (2 / (1 + β)) := by sorry
end WeightedMajority.Basic
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.