Skip to main content
PathsHoeffding lemma

Theorem trail

Hoeffding lemma

The MGF control that turns boundedness into sub-Gaussian tails.

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
lemma
Evidence level
Exact Lean wrapper
Source precision
reviewed / A
Diagnostics
1 item
Exercises
1 exercise
Failure checks
2 checks
Open Atlas traceOpen evidence recordJump to sourcesJump to failures

Theorem Statement

Bounded random variables cannot have heavy tails. They literally cannot take values beyond . Hoeffding's lemma quantifies this: the MGF of any bounded centered variable is dominated by a Gaussian MGF. The factor of comes from a convexity argument applied to on the interval .

Assumptions

  • X is bounded in [a,b]
  • E[X] = 0

Proof Sketch

For a centered bounded variable, bound the exponential moment by the chord between the endpoint exponentials. Optimizing the resulting convex upper bound gives exp(lambda^2(b-a)^2/8). That MGF domination is the sub-Gaussian certificate.

Proof Obligations

Centered variable with bounded support

assumption

Verify E[X] = 0 and a <= X <= b before using the endpoint-width certificate in the exponential-moment bound.

Missing centering or an unbounded tail breaks the sub-Gaussian MGF certificate produced by the lemma.

Endpoint chord controls the exponential

proof step

The proof uses convexity of exp to dominate e^{lambda X} by the chord through the interval endpoints, then optimizes the resulting scalar bound.

Replacing the chord argument with a variance heuristic loses the source of the 1/8 constant.

Support-width control is worst-case

boundary

The lemma treats all distributions with the same interval width by the same certificate, even when their actual variance is much smaller.

Using Hoeffding's lemma as a tight distribution-specific estimate can overstate precision.

Centering is part of the MGF certificate

boundary

If the random variable is not centered, subtract its expectation before applying the bounded-width MGF certificate.

Dropping the centering condition moves the linear term into the exponent and changes the theorem being used.

Source Locators

High-Dimensional Statistics (2019)

proof

Chapter 2 — Basic tail and concentration bounds

wainwright-2019:ch2

kind
chapter
review
reviewed / A
extract
manual

Chapter-level support for sub-Gaussian MGF bounds and Hoeffding-style bounded-variable concentration.

Concentration Inequalities (2013)

proof

Chapter 2 — Basic concentration tools

boucheron-lugosi-massart-2013:ch2

kind
chapter
review
reviewed / B
extract
manual

Chapter-level support for Hoeffding's lemma as a basic concentration tool.

High-Dimensional Statistics (2019)

proof

Proposition 2.5 — Hoeffding bound

wainwright-2019:prop2.5

kind
proposition
review
reviewed / A
extract
manual
number
2.5

Anchor: Hoeffding bound

Reviewed proposition-level support connecting bounded variables to Hoeffding-style sub-Gaussian control.

Concentration Inequalities (2013)

proof

Lemma 2.2 — Hoeffding's lemma

boucheron-lugosi-massart-2013:lem2.2

kind
lemma
review
reviewed / A
extract
manual
number
2.2

Anchor: Hoeffding's lemma

Reviewed lemma-level support for Hoeffding's lemma.

Curated Trace

  1. 1
    Bounded variableinput

    The theorem starts from support information, not variance alone.

    Checkpoint

    Record both endpoints a and b.

  2. 2
    MGF comparisonmethod

    Tail bounds will come from exponential moments.

    Checkpoint

    Centering E[X] = 0 is part of the statement.

  3. 3
    Convex chord boundcalculus step

    Convexity of exp lets the endpoint chord dominate the graph on [a,b].

    Checkpoint

    The constant 1/8 comes from optimizing this upper envelope.

  4. 4
    Sub-Gaussian certificatelemma

    The bounded centered variable now has Gaussian-type MGF control.

    Checkpoint

    Worst-case bounded support is not the same as variance-sensitive tightness.

Failure Modes

Support-width control is worst-case

The lemma treats all distributions with the same interval width by the same certificate, even when their actual variance is much smaller.

Risk: Using Hoeffding's lemma as a tight distribution-specific estimate can overstate precision.

Check: The lemma treats all distributions with the same interval width by the same certificate, even when their actual variance is much smaller.

Centering is part of the MGF certificate

If the random variable is not centered, subtract its expectation before applying the bounded-width MGF certificate.

Risk: Dropping the centering condition moves the linear term into the exponent and changes the theorem being used.

Check: If the random variable is not centered, subtract its expectation before applying the bounded-width MGF certificate.