Chernoff bounding lemma

Definitions and notation

• Probability measure , expectation .
• Moment generating function (exponential moments).
• Legendre transform and rate function (for the optimized form).

Statement

Let $X$ be a real-valued random variable. Fix $a\in\mathbb R$.

1. Upper tail. For any $t>0$ such that $\mathbb E[e^{tX}]<\infty$,

   $$\mathbb P(X \ge a) \le e^{-t a}\,\mathbb E[e^{tX}].$$

2. Lower tail. For any $t<0$ such that $\mathbb E[e^{tX}]<\infty$,

   $$\mathbb P(X \le a) \le e^{-t a}\,\mathbb E[e^{tX}].$$

Equivalently, for the upper tail,

whenever the infimum is over $t$ with finite exponential moment.

Key hypotheses and conclusions

Hypotheses

• Exponential moment exists at the chosen tilt $t$: $\mathbb E[e^{tX}]<\infty$.
• $t>0$ for upper tails, $t<0$ for lower tails.

Conclusions

• Tail probabilities are controlled by exponential moments.
• Optimizing over $t$ yields the tightest Chernoff bound available from the moment generating function (often expressed via a Legendre transform of $\log \mathbb E[e^{tX}]$).

Proof idea / significance

Apply Markov’s inequality to the nonnegative random variable $e^{tX}$:

The optimized bound connects directly to large deviations: the function $t\mapsto \log \mathbb E[e^{tX}]$ is convex, and its Legendre transform often appears as the candidate rate function in a large deviation principle .

In statistical mechanics, the same mechanism controls fluctuations of extensive observables via exponential tilting of ensembles.