Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 8, p. 22 — Azuma–Hoeffding inequality for the running maximum of a martingale

Proved
SeqRankAgg.Optimality.lemma_8

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

azuma-hoeffdingconcentrationmartingalep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1

Let (Mn)n≥0(M_n)_{n\ge0}(Mn​)n≥0​ be a real martingale with respect to a filtration (Fn)(\mathcal F_n)(Fn​) on a probability space (Ω,F,P)(\Omega,\mathcal F,\mathbb P)(Ω,F,P), started at M0=0M_0=0M0​=0. Suppose its increments Xn=Mn−Mn−1X_n=M_n-M_{n-1}Xn​=Mn​−Mn−1​ satisfy an≤Xn≤bna_n\le X_n\le b_nan​≤Xn​≤bn​ almost surely, for deterministic constants an≤bna_n\le b_nan​≤bn​. Then for every n≥1n\ge1n≥1 and every t>0t>0t>0,

P(max⁡1≤k≤nMk≥t)≤exp⁡(−2t2∑i=1n(bi−ai)2).\mathbb P\Big(\max_{1\le k\le n}M_k\ge t\Big)\le\exp\Big(-\frac{2t^2}{\sum_{i=1}^n(b_i-a_i)^2}\Big).P(1≤k≤nmax​Mk​≥t)≤exp(−∑i=1n​(bi​−ai​)22t2​).

This maximal form of the Azuma–Hoeffding inequality is the concentration tool the paper applies to the log-likelihood martingales in the lower-bound and sample-size arguments.

Formalization Note The page leaves M0M_0M0​ implicit; the Lean statement assumes M0=0M_0=0M0​=0 almost surely, without which the bound fails (a constant martingale Mn≡M0>tM_n\equiv M_0>tMn​≡M0​>t). Time is indexed from 000 and the increment bounds are indexed by the later time. If ∑i(bi−ai)2=0\sum_i(b_i-a_i)^2=0∑i​(bi​−ai​)2=0, Lean's division gives the trivial bound 111.

Preamble
import Mathlib

open MeasureTheory ProbabilityTheory Filter
open scoped ENNReal
Formal statement
namespace SeqRankAgg.Optimality

theorem lemma_8 {Ω : Type*} [mΩ : MeasurableSpace Ω] (P : Measure Ω) [IsProbabilityMeasure P]
    (ℱ : Filtration ℕ mΩ) (M : ℕ → Ω → ℝ) (hM : Martingale M ℱ P)
    (hM0 : ∀ᵐ ω ∂P, M 0 ω = 0)
    (a b : ℕ → ℝ)
    (hinc : ∀ k : ℕ, ∀ᵐ ω ∂P, M (k + 1) ω - M k ω ∈ Set.Icc (a (k + 1)) (b (k + 1)))
    (n : ℕ) (hn : 1 ≤ n) (t : ℝ) (ht : 0 < t) :
    P {ω | ∃ k ∈ Finset.Icc 1 n, t ≤ M k ω} ≤
      ENNReal.ofReal (Real.exp (-(2 * t ^ 2 / ∑ i ∈ Finset.Icc 1 n, (b i - a i) ^ 2))) := by sorry

end SeqRankAgg.Optimality
Source
Chen, Chen & Li, Asymptotically optimal sequential design for rank aggregation, arXiv:1710.06056v1, p. 22, Lemma 8 (Azuma 1967; Hoeffding 1963)
Human review
  • Endorsed by Shuze Chen · Oct 20, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 20, 2026

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

  • Endorsed by Community (Bot) · Nov 11, 2026

    Confirmed by the moderator at approval.

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