A maximal Azuma–Hoeffding inequality along i.i.d. uniform rounds #
Martingale concentration in the finite-probability layer: a process X_{j+1} = step X_j ρ_j
driven by i.i.d. uniform rounds ρ_j : R (expectations by expList), and increments
D (X_j) ρ_j with zero conditional mean, avg (D y) = 0 for every state y, and bounded by c.
Their partial sums M_k = incrementSum step D x (l.take k) form a martingale, and
P(∃ k ≤ n, M_k ≥ λ) ≤ exp(-λ² / (2 n c²))
(K. Azuma, Weighted sums of certain dependent random variables, Tôhoku Math. J. 19, 1967;
W. Hoeffding, J. Amer. Statist. Assoc. 58, 1963, Theorem 2 for the independent case), in the
maximal form obtained from Ville's (Doob's) maximal inequality for the exponential supermartingale
exp(θ M_k - k θ² c² / 2).
incrementSum: the partial sums, additive and monotone in the increments (incrementSum_add,incrementSum_mono), withincrementSum_mul_sub,incrementSum_neg,incrementSum_telescope(incrementsφ (step y a) - φ y - ψ ytelescope) andincrementSum_take(the sum of a state function along the firstkrounds);avg_exp_mul_le: Hoeffding's lemma for a centred variable bounded bycunder a uniform draw,avg (exp (θ f)) ≤ exp (θ² c² / 2)(convexity ofexp, thenReal.cosh_le_exp_half_sq);expList_ville: Ville's maximal inequality for a multiplicative processexp (M x l)withM x (a :: l) = E x a + M (step x a) landavg (exp (E y ·)) ≤ 1(a nonnegative supermartingale started at1): it reachesμ > 0withinnrounds with probability at most1 / μ. Proved by induction onn, peeling off the first round;expList_exp_incrementSum_le: the exponential supermartingale bound𝔼[exp (incrementSum step D x l) · F (state)] ≤ F xwhen one round does not increaseexp D · Fin expectation;expList_azuma: the maximal Azuma–Hoeffding inequality.
The state type σ is arbitrary (not necessarily finite), so this covers every martingale with
respect to the rounds: take for σ the histories List R.
Why not Mathlib. Mathlib's Azuma–Hoeffding inequality
(ProbabilityTheory.measure_sum_ge_le_of_hasCondSubgaussianMGF) is measure-theoretic (a
filtration, conditional sub-Gaussian MGFs) and bounds P(M_n ≥ λ) at the final time only, not
P(∃ k ≤ n, M_k ≥ λ); its Hoeffding lemma (hasSubgaussianMGF_of_mem_Icc_of_integral_eq_zero)
is stated for integrals. Using them would need a bridge from avg/expList to measures on the
path space, which this library avoids. Dynamics.Concentration and Dynamics.Chernoff only
treat sums of independent coordinates (with Hoeffding's lemma for Bernoulli variables,
one_sub_add_mul_exp_le), hence the elementary proofs here.
Sums of increments along the rounds #
The sum ∑_{j < |l|} D (X_j) (l_j) of the increments D along the rounds l, for the process
X_0 = x, X_{j+1} = step X_j l_j. When every avg (D y) vanishes,
k ↦ incrementSum step D x (l.take k) is a martingale along i.i.d. uniform rounds l.
Equations
- Dynamics.incrementSum step D x [] = 0
- Dynamics.incrementSum step D x (a :: l_2) = D x a + Dynamics.incrementSum step D (step x a) l_2
Instances For
Sums of increments are additive in the increments.
incrementSum of the affine increments θ D - b (the exponent of the exponential
supermartingale).
Negated increments.
Increments of the form φ (step y a) - φ y - ψ y telescope.
The sum of a state function along the first k rounds.
Hoeffding's lemma, Ville's inequality and Azuma–Hoeffding #
Ville's maximal inequality along i.i.d. uniform rounds (finite horizon). Let
M x (a :: l) = E x a + M (step x a) l, M x [] = 0, with avg (exp (E y ·)) ≤ 1 for every
y, so that k ↦ exp (M x (l.take k)) is a nonnegative supermartingale started at 1. Then it
reaches μ > 0 at some step k ≤ n with probability at most 1 / μ.
Exponential supermartingale along i.i.d. uniform rounds (finite horizon). If one round
never increases exp (D y ·) · F (step y ·) in expectation, avg (exp (D y a) F (step y a)) ≤ F y,
then exp (incrementSum step D x l) · F (l.foldl step x) has expectation at most F x after any
number n of rounds. With F = 1 it is the fixed-time bound for the supermartingale of
expList_ville.
Maximal Azuma–Hoeffding inequality (Azuma 1967; Hoeffding 1963, Theorem 2, for independent
summands). If the increments have zero mean over a uniform round, avg (D y) = 0, and are bounded,
|D y a| ≤ c, then over n i.i.d. uniform rounds the martingale
M_k = incrementSum step D x (l.take k) reaches λ ≥ 0 at some step k ≤ n with probability at
most exp(-λ² / (2 n c²)).