Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

§6, proof of Theorem 6.1 — the expected number of mistakes of WMR equals E∑j∣γ(j)−ρ(j)∣\mathbf E\sum_j|\gamma^{(j)}-\rho^{(j)}|E∑j​∣γ(j)−ρ(j)∣

Proved
WeightedMajority.Randomized.expected_mistakes_eq

by mikedeng1 · Oct 6, 2026 · Mathlib 0df444a (Lean v4.33.1)

conditional-expectationonline-learningp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1randomized-algorithmsweighted-majority

Consider the randomized master algorithm WMR on ttt trials, with a pool of nnn algorithms whose predictions xi(j)x_i^{(j)}xi(j)​ lie in [0,1][0,1][0,1], binary labels ρ(j)\rho^{(j)}ρ(j), binary master predictions λ(j)\lambda^{(j)}λ(j), 0≤β<10 \le \beta < 10≤β<1, positive initial weights, and update factors satisfying (5.1). Let γ(j)\gamma^{(j)}γ(j) be the weighted average prediction of the pool in trial jjj and m=∑j=1t∣λ(j)−ρ(j)∣m = \sum_{j=1}^t |\lambda^{(j)}-\rho^{(j)}|m=∑j=1t​∣λ(j)−ρ(j)∣ the number of mistakes of WMR. Suppose the weak independence condition holds. Then, for every trial j=1,…,tj = 1,\dots,tj=1,…,t,

E(∣λ(j)−ρ(j)∣ ∣ (x(1),ρ(1)),…,(x(j),ρ(j)))=∣γ(j)−ρ(j)∣almost surely,\mathbf E\big(|\lambda^{(j)}-\rho^{(j)}| \,\big|\, (x^{(1)},\rho^{(1)}),\dots,(x^{(j)},\rho^{(j)})\big) = |\gamma^{(j)}-\rho^{(j)}| \quad\text{almost surely},E(∣λ(j)−ρ(j)∣​(x(1),ρ(1)),…,(x(j),ρ(j)))=∣γ(j)−ρ(j)∣almost surely,

and consequently

E(m)=E(∑j=1t∣λ(j)−ρ(j)∣)=E(∑j=1t∣γ(j)−ρ(j)∣).\mathbf E(m) = \mathbf E\Big(\sum_{j=1}^t |\lambda^{(j)}-\rho^{(j)}|\Big) = \mathbf E\Big(\sum_{j=1}^t |\gamma^{(j)}-\rho^{(j)}|\Big).E(m)=E(j=1∑t​∣λ(j)−ρ(j)∣)=E(j=1∑t​∣γ(j)−ρ(j)∣).

This identity reduces the expected number of mistakes of the randomized algorithm to the total absolute loss of the deterministic weighted-average master WMC on the same weights, so that the pathwise loss bound for WMC applies.

Formalization Note Both expectations are Bochner integrals of bounded measurable functions (each summand lies in [0,1][0,1][0,1]), so no integrability hypothesis is needed. Trials are indexed from 000 to t−1t-1t−1 in Lean.

Preamble
import Mathlib
import Definitions.Def_WeightedMajority_Randomized_WMRModel

open MeasureTheory
Formal statement
namespace WeightedMajority.Randomized

/-- §6, p. 240, proof of Theorem 6.1: under the weak independence condition the conditional
expected mistake indicator of each trial is `|γ^{(j)} − ρ^{(j)}|`, and the expected number of
mistakes of WMR equals the expected total loss `E(Σ_j |γ^{(j)} − ρ^{(j)}|)`. -/
theorem expected_mistakes_eq {Ω : Type*} [MeasurableSpace Ω] (P : Measure Ω)
    [IsProbabilityMeasure P] {n t : ℕ} (β : ℝ) (w1 : Fin n → ℝ)
    (F : ℕ → Fin n → ℝ → ℝ → ℝ) (x : ℕ → Fin n → Ω → ℝ) (ρ lam : ℕ → Ω → ℝ)
    (hM : IsWMRModel t β w1 F x ρ lam)
    (hweak : WeakIndependence P t w1 F x ρ lam) :
    (∀ j < t, P[fun ω => |lam j ω - ρ j ω| | history x ρ j]
        =ᵐ[P] fun ω => |gamma w1 F x ρ j ω - ρ j ω|) ∧
    ∫ ω, mistakes t lam ρ ω ∂P
      = ∫ ω, ∑ j ∈ Finset.range t, |gamma w1 F x ρ j ω - ρ j ω| ∂P := by sorry

end WeightedMajority.Randomized
Source
Littlestone, Warmuth, The Weighted Majority Algorithm, Inform. and Comput. 108 (1994), p. 240, Section 6, proof of Theorem 6.1
Human review
  • Endorsed by Shuze Chen · Oct 6, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 6, 2026

    Confirmed by the mission captain (proposal self-audit).

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