Chernoff Bounds from Moment Generating Functions

Why Exponentials Help Bound Deviations

A deviation event for a sample average is a statement about a sum. For example, an average exceeding its mean by \(t\) means that the sum of the centered observations is at least \(nt\). Markov’s inequality can bound this event after an exponential transformation: large values of the sum produce especially large values of its exponential. The free exponential parameter can then be chosen to make the bound as small as possible.

This method gives a Chernoff bound. Its usefulness depends on the moment-generating function (MGF), which records exponential moments and may exist even when the observations are unbounded. The method does not guarantee a sharp bound, but it gives a systematic way to obtain one-sided tail guarantees and makes the role of independence explicit.

Definition: The moment-generating function of a random variable \(X\) is \(M_X(\lambda)=E[e^{\lambda X}]\), at each real \(\lambda\) for which this expectation is finite. If \(E[X]=\mu\), its centered log-MGF is \(K_X(\lambda)=\log E[e^{\lambda(X-\mu)}]\), wherever the expectation is finite.

At \(\lambda=0\), \(M_X(0)=1\) and \(K_X(0)=0\). Positive values of \(\lambda\) are used to bound upper tails; negative values can be used for lower tails. A Chernoff bound is informative only when the needed exponential moment is finite. The optimization below is over admissible values of the parameter, not over values at which the MGF is infinite.

The One-Sided Chernoff Bound

First consider independent observations \(X_1,\ldots,X_n\), each with finite mean \(\mu_i=E[X_i]\). They need not have the same distribution. For a positive deviation \(t\), define the centered sum \(S=\sum_{i=1}^n(X_i-\mu_i)\). For any admissible \(\lambda>0\), Markov’s inequality gives

P\left(\frac{1}{n}\sum_{i=1}^n(X_i-\mu_i)\ge t\right) =P(e^{\lambda S}\ge e^{\lambda nt}) \le e^{-\lambda nt}E[e^{\lambda S}].

Independence gives \(E[e^{\lambda S}]=\prod_{i=1}^n E[e^{\lambda(X_i-\mu_i)}]\). This factorization is the specific step that requires independence. Optimizing the bound over \(\lambda\) yields the following result.

Theorem (Chernoff bound for an independent average): Suppose \(X_1,\ldots,X_n\) are independent, have finite means \(\mu_i\), and have finite centered MGFs at the parameter values considered. Let \(K_i(\lambda)=\log E[e^{\lambda(X_i-\mu_i)}]\). Then

P\left(\frac{1}{n}\sum_{i=1}^n(X_i-\mu_i)\ge t\right) \le \inf_{\substack{\lambda>0\\K_i(\lambda)<\infty\ \forall i}} \exp\left\{-\lambda nt+\sum_{i=1}^n K_i(\lambda)\right\}.

If there is no positive admissible parameter, this method gives no nontrivial upper bound. The infimum notation also covers cases where the best value is approached but not attained.

Proof. For any admissible \(\lambda>0\), \(e^{\lambda S}\) is nonnegative. On the event \(S\ge nt\), it is at least \(e^{\lambda nt}\). Markov’s inequality therefore bounds the event probability by \(e^{-\lambda nt}E[e^{\lambda S}]\). Since the observations are independent,

E[e^{\lambda S}] =E\left[\prod_{i=1}^n e^{\lambda(X_i-\mu_i)}\right] =\prod_{i=1}^n E[e^{\lambda(X_i-\mu_i)}] =\exp\left\{\sum_{i=1}^n K_i(\lambda)\right\}.

This proves the stated bound for each admissible \(\lambda>0\). Taking the infimum over those values proves the result. \(\square\)

For the lower tail, apply the same argument to \(-S\). For any admissible \(\lambda>0\),

P\left(\frac{1}{n}\sum_{i=1}^n(X_i-\mu_i)\le -t\right) \le \exp\left\{-\lambda nt+\sum_{i=1}^n K_i(-\lambda)\right\}.

When the observations are identically distributed with mean \(\mu\) and centered log-MGF \(K\), the upper-tail result simplifies to

P\left(\frac{1}{n}\sum_{i=1}^n X_i-\mu\ge t\right) \le \inf_{\lambda>0}\exp\{-n(\lambda t-K(\lambda))\} =\exp\left\{-n\sup_{\lambda>0}(\lambda t-K(\lambda))\right\},

where the optimization uses only admissible \(\lambda\), and the supremum may include \(\lambda=0\) without changing the bound. The quantity \(\sup_{\lambda\ge 0}(\lambda t-K(\lambda))\) is the one-sided rate supplied by this MGF calculation. If the supremum is attained at an interior point and \(K\) is differentiable there, the optimizing parameter satisfies \(K'(\lambda)=t\). This equation is a way to locate a candidate optimizer, not a guarantee that an interior optimizer exists.

Worked Examples

Worked Example: A Bernoulli Sample Average

Let \(X_1,\ldots,X_{20}\) be independent Bernoulli observations with success probability \(p=0.3\). Bound the probability that their average is at least \(q=0.5\).

For one observation, \(E[e^{\lambda X_i}]=1-p+pe^\lambda\). Applying Markov’s inequality to the sum gives, for \(\lambda>0\),

P\left(\frac{1}{20}\sum_{i=1}^{20}X_i\ge q\right) \le \exp\{-20\lambda q\}(1-p+pe^\lambda)^{20}.

To minimize this expression, minimize its log per observation, \(-\lambda q+\log(1-p+pe^\lambda)\). Differentiating and setting the derivative to zero gives

-q+\frac{pe^\lambda}{1-p+pe^\lambda}=0, \qquad e^{\lambda_*}=\frac{q(1-p)}{p(1-q)} =\frac{0.5(0.7)}{0.3(0.5)}=\frac{7}{3}.

This is an admissible positive parameter because \(q>p\). Substitution gives the optimized bound \(\exp\{-20D(q\|p)\}\), where here \(D(q\|p)=q\log(q/p)+(1-q)\log((1-q)/(1-p))\). Numerically,

D(0.5\|0.3) =0.5\log(5/3)+0.5\log(5/7) =0.5\log(25/21)\approx 0.08718, \qquad P(\bar X\ge0.5)\le e^{-1.7436}\approx0.175.

The inequality is a bound, not an assertion that the event has probability \(0.175\). The parameter was selected to give the smallest bound in this exponential family.

Worked Example: A Poisson Sample Average

Let \(X_1,\ldots,X_5\) be independent Poisson random variables with mean \(1\). Find a Chernoff bound for the event that their average is at least \(2\).

For a Poisson random variable with mean \(1\), \(E[e^{\lambda X_i}]=\exp(e^\lambda-1)\). The exponential Markov bound is therefore

P\left(\frac{1}{5}\sum_{i=1}^5X_i\ge2\right) \le\exp\{-5(2\lambda-(e^\lambda-1))\},\qquad \lambda>0.

The exponent is maximized by setting the derivative of \(2\lambda-(e^\lambda-1)\) equal to zero: \(2-e^\lambda=0\), so \(\lambda_*=\log 2\). This gives

P(\bar X\ge2) \le\exp\{-5(2\log 2-1)\} \approx e^{-1.9315}\approx0.145.

The Poisson observations are unbounded, but their MGF is finite at the optimizing parameter \(\log 2\). Boundedness is not needed for this calculation; the relevant requirement is that the required exponential moment exists.

Worked Example: A Normal Sample Average

Suppose \(X_1,\ldots,X_{16}\) are independent with \(X_i\sim N(\mu,4)\), so each observation has variance \(4\). Bound the probability that the sample average exceeds \(\mu\) by at least \(1\).

The centered MGF of one observation is \(E[e^{\lambda(X_i-\mu)}]=e^{2\lambda^2}\), so \(K(\lambda)=2\lambda^2\). The exponent to maximize is \(\lambda t-K(\lambda)\), with \(t=1\). Its derivative is \(1-4\lambda\), giving \(\lambda_*=1/4\). Hence

P(\bar X-\mu\ge1) \le\exp\{-16[(1/4)-2(1/4)^2]\} =e^{-2}\approx0.1353.

The optimizer is positive, as required for an upper-tail bound. The calculation uses the MGF method; in this normal case it also recovers the familiar exponential form based on the variance.

What Optimization Does—and Does Not—Guarantee

For each fixed admissible parameter, exponential Markov gives a valid inequality. Optimization selects the strongest inequality in that family. In smooth examples, solving \(K'(\lambda)=t\) often identifies the optimum, as in the worked examples. If the equation has no admissible solution, or if the MGF is finite only on a restricted interval, the infimum formulation remains the correct one. One should not substitute a parameter outside the MGF’s domain.

The method matters because the MGF can encode tail behavior more sharply than a bound based only on a variance, and it applies to distributions beyond bounded observations. In learning problems, tail bounds for averages help control deviations of empirical quantities from their expectations. This tutorial supplies the general exponential argument; the resulting numerical strength depends on the distributional information available about the observations.

Common Mistake: Assuming Independence Without Checking

A tempting but invalid argument is to compute each observation’s MGF and multiply those values even when the observations are dependent. The identity \(E[\prod_i W_i]=\prod_i E[W_i]\) generally requires independence of the \(W_i\). Without it, the proof of the sample-average Chernoff bound does not go through.

For a concrete check, let \(Z\) take values \(-1\) and \(1\) with equal probability, and set \(X_1=X_2=Z\). Each observation has mean zero, but they are perfectly dependent. The event \((X_1+X_2)/2\ge0.9\) has probability \(1/2\), since it occurs exactly when \(Z=1\). If one incorrectly treated the observations as independent, the Bernoulli-style rate for a Rademacher average at \(0.9\) would give the bound \(\exp\{-2D(0.95\|0.5)\}\approx0.372\), which is smaller than the true probability. The contradiction exposes the invalid factorization. For dependent data, a different argument or additional assumptions are needed.

Key takeaway: Apply Markov’s inequality to an exponential, factor the MGF only when independence justifies it, and optimize over parameters where the MGF is finite. The resulting bound is one-sided and can be useful even for unbounded observations.

Check Your Understanding

Use the definitions and derivations above to answer these questions.

For an upper-tail bound, why must the exponential parameter be positive?
In the independent-average proof, which equality uses independence?
For independent Poisson observations with mean \(1\), what parameter optimizes the Chernoff bound for an average threshold of \(3\)?
What should be done if the formal optimizing parameter lies outside the interval where the MGF is finite?
Why is multiplying the marginal MGFs not justified for dependent observations?