Skip to main content
PathsAzuma-Hoeffding martingale tail

Theorem trail

Azuma-Hoeffding martingale tail

The bounded-difference concentration route for adaptive sequences.

Open topicExplore AtlasClaim evidenceEvidence panel

Record

Research Record

A compact audit view for the theorem before the full source, proof, diagnostic, and failure-mode sections.

Claim scope
theorem
Evidence level
Lean dependency verified
Source precision
reviewed / B
Diagnostics
4 items
Exercises
1 exercise
Failure checks
2 checks
Open Atlas traceOpen evidence recordJump to sourcesJump to failures

Theorem Statement

Let be a martingale with bounded increments: almost surely for . Then for any : If all (equal bounds), this simplifies to .

Assumptions

  • (M_n) is a martingale
  • martingale increments are bounded almost surely by constants c_k

Proof Sketch

Treat the centered increments as a martingale difference sequence and control each conditional exponential moment from the bounded-increment assumption. Iterating the conditional MGF bound gives a sub-Gaussian MGF for the martingale difference sum. Chernoff optimization then yields the one-sided tail; a second application to the negative martingale gives the two-sided display.

Proof Obligations

Adapted martingale differences with bounded increments

assumption

Verify the filtration, adaptedness, conditional-mean-zero property, and increment bounds before replacing iid assumptions with Azuma-Hoeffding.

A learner-history process that is merely centered marginally is not enough for the martingale tail theorem.

Iterated conditional MGF control

proof step

The proof repeatedly conditions on the past, applies the bounded-increment exponential-moment bound, and then uses Chernoff optimization.

Factoring MGFs as if the increments were iid would prove the wrong theorem for adaptive sequences.

Worst-case increment scale, not variance-adaptive

boundary

Azuma-Hoeffding uses the sum of squared increment bounds; variance-sensitive behavior needs Freedman or Bernstein-style martingale tools.

Using Azuma as a calibrated variance estimate can make adaptive diagnostic uncertainty look sharper than it is.

Conditional mean zero is stronger than marginal zero

boundary

Check the martingale-difference condition against the learner history filtration; marginal centering alone is not enough.

Treating adaptively chosen increments as merely average-zero can invalidate the conditional MGF iteration.

Source Locators

Concentration Inequalities (2013)

proof

Chapter 3 — Bounded differences and exponential concentration

boucheron-lugosi-massart-2013:ch3

kind
chapter
review
reviewed / B
extract
manual

Chapter-level support for bounded-difference and martingale concentration arguments, including Azuma-Hoeffding-style bounds.

High-Dimensional Statistics (2019)

proof

Corollary 2.20 — Azuma-Hoeffding

wainwright-2019:cor2.20

kind
corollary
review
reviewed / A
extract
manual
number
2.20

Anchor: Azuma-Hoeffding

Reviewed corollary-level support for the Azuma-Hoeffding martingale tail bound.

Curated Trace

  1. 1
    Martingale differencessetup

    The theorem applies when each increment has conditional mean zero given the past.

    Checkpoint

    Check filtration and adaptedness before checking increment bounds.

  2. 2
    Conditional MGF controlproof method

    Bounded increments supply the exponential-moment control used by Chernoff's method.

    Checkpoint

    The current Lean artifact verifies a conditional sub-Gaussian one-sided bridge.

  3. 3
    Hoeffding-style tailtail conversion

    The MGF bound converts into a Gaussian-type deviation inequality.

    Checkpoint

    The scale is sqrt(sum c_k^2), not a variance-adaptive Freedman scale.

  4. 4
    Adaptive replay usesystem use

    Adaptive diagnostic analysis needs martingale conditions when iid assumptions fail.

    Checkpoint

    Do not reuse iid Hoeffding unless the feedback process actually preserves iid sampling.

Failure Modes

Worst-case increment scale, not variance-adaptive

Azuma-Hoeffding uses the sum of squared increment bounds; variance-sensitive behavior needs Freedman or Bernstein-style martingale tools.

Risk: Using Azuma as a calibrated variance estimate can make adaptive diagnostic uncertainty look sharper than it is.

Check: Azuma-Hoeffding uses the sum of squared increment bounds; variance-sensitive behavior needs Freedman or Bernstein-style martingale tools.

Conditional mean zero is stronger than marginal zero

Check the martingale-difference condition against the learner history filtration; marginal centering alone is not enough.

Risk: Treating adaptively chosen increments as merely average-zero can invalidate the conditional MGF iteration.

Check: Check the martingale-difference condition against the learner history filtration; marginal centering alone is not enough.