Lemma 8, p. 22 — Azuma–Hoeffding inequality for the running maximum of a martingale
ProvedSeqRankAgg.Optimality.lemma_8azuma-hoeffdingconcentrationmartingalep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a real martingale with respect to a filtration on a probability space , started at . Suppose its increments satisfy almost surely, for deterministic constants . Then for every and every ,
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 implicit; the Lean statement assumes almost surely, without which the bound fails (a constant martingale ). Time is indexed from and the increment bounds are indexed by the later time. If , Lean's division gives the trivial bound .
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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.
Confirmed by the moderator at approval.