Lower-Tail Chernoff Bounds for Nonnegative Sums

Why Negative Exponential Parameters Bound Lower Tails

For a sum of nonnegative random variables, an unusually small value is a lower-tail event. The exponential Markov inequality can bound it by applying Markov's inequality not to the sum itself, but to its negative exponential. When the sum is small, its negative exponential is large; this reverses the direction in which the event is represented and makes an upper-tail inequality useful for a lower-tail question.

The parameter domain matters. For nonnegative $X$, $e^{-\lambda X}\leq 1$ whenever $\lambda\geq 0$, so its expectation exists for every such $\lambda$. This is the key advantage of the negative exponent here: no positive moment-generating-function domain needs to be checked.

Definition: Let $X_1,\ldots,X_n$ be independent, nonnegative random variables, and let $S_n=\sum_{i=1}^n X_i$. For $\lambda\geq 0$, define the Laplace transform of $X_i$ at $\lambda$ by $L_i(\lambda)=E[e^{-\lambda X_i}]$. It satisfies $0<L_i(\lambda)\leq 1$. If the variables are identically distributed as $X$, write $L(\lambda)=E[e^{-\lambda X}]$.

The Lower-Tail Chernoff Bound

Fix a threshold $a\geq 0$ and choose $\lambda>0$. On the event $S_n\leq a$, multiplying by $-\lambda$ reverses the inequality, so $-\lambda S_n\geq-\lambda a$. Exponentiating gives $e^{-\lambda S_n}\geq e^{-\lambda a}$. Markov's inequality can therefore be applied to the nonnegative random variable $e^{-\lambda S_n}$.

Theorem: If $X_1,\ldots,X_n$ are independent and nonnegative, then for every $a\geq 0$ and $\lambda>0$, $$ P(S_n\leq a) \leq e^{\lambda a}E[e^{-\lambda S_n}] = e^{\lambda a}\prod_{i=1}^n L_i(\lambda). $$ If the $X_i$ are identically distributed, this becomes $$ P(S_n\leq a)\leq e^{\lambda a}L(\lambda)^n. $$

Proof. Since $e^{-\lambda S_n}$ is nonnegative, Markov's inequality gives

P(S_n\leq a) =P(e^{-\lambda S_n}\geq e^{-\lambda a}) \leq \frac{E[e^{-\lambda S_n}]}{e^{-\lambda a}} =e^{\lambda a}E[e^{-\lambda S_n}].

Independence and $S_n=\sum_{i=1}^n X_i$ imply

E[e^{-\lambda S_n}] =E\left[\prod_{i=1}^n e^{-\lambda X_i}\right] =\prod_{i=1}^n E[e^{-\lambda X_i}] =\prod_{i=1}^n L_i(\lambda).

The expectations are finite because each factor lies between zero and one. If the variables are identically distributed, every factor is $L(\lambda)$, yielding $L(\lambda)^n$. $\square$

Every $\lambda>0$ gives a valid bound, but not every choice is useful. Since a probability is also at most one, the practical bound is the smaller of one and the exponential expression. Optimizing over the parameter gives

P(S_n\leq a)\leq \min\left\{1,\ \inf_{\lambda>0} \left[e^{\lambda a}\prod_{i=1}^n L_i(\lambda)\right]\right\}.

For identically distributed summands and a threshold $a=nx$, the expression to minimize is $[e^{\lambda x}L(\lambda)]^n$. Thus the per-summand quantity $e^{\lambda x}L(\lambda)$ determines whether a chosen parameter improves the trivial bound.

When a Positive Parameter Improves the Bound

If the mean $\mu=E[X]$ is finite and the threshold per summand $x$ is below $\mu$, a sufficiently small positive parameter gives a bound below one. The following argument makes that local claim precise; it does not promise that a large parameter is useful.

Result: Suppose $X\geq 0$ and $E[X]=\mu<\infty$. Define $g(\lambda)=\lambda x+\log L(\lambda)$ for $\lambda\geq 0$, where $L(\lambda)=E[e^{-\lambda X}]$. Then $g(0)=0$ and the right derivative at zero is $g'(0+)=x-\mu$. Consequently, if $x<\mu$, then $g(\lambda)<0$ for all sufficiently small positive $\lambda$, and the identically distributed lower-tail bound at $a=nx$ is strictly less than one for those choices.

Proof. For $\lambda>0$,

\frac{L(\lambda)-1}{\lambda} =E\left[\frac{e^{-\lambda X}-1}{\lambda}\right].

For each fixed finite value of $X$, the integrand converges to $-X$ as $\lambda\downarrow0$. Also,

\left|\frac{e^{-\lambda X}-1}{\lambda}\right| =\frac{1-e^{-\lambda X}}{\lambda}\leq X,

because $1-e^{-u}\leq u$ for $u\geq0$. The integrable dominating variable is $X$, so dominated convergence gives $L'(0+)=-\mu$. Since $L(0)=1$, the right derivative of $\log L(\lambda)$ at zero is also $-\mu$. Hence $g'(0+)=x-\mu$. When $x<\mu$, this derivative is negative, so the definition of the right derivative implies $g(\lambda)<g(0)=0$ for all sufficiently small positive $\lambda$. The bound is $\exp(ng(\lambda))<1$. $\square$

Worked Examples

Worked Example: A Lower Tail for a Binomial Sum

Let $X_1,\ldots,X_n$ be independent Bernoulli random variables with success probability $p=0.6$. Find the optimized Chernoff bound for $P(S_n\leq 0.4n)$, where $S_n=\sum_{i=1}^n X_i$.

For one summand, $L(\lambda)=0.4+0.6e^{-\lambda}$. The bound is

P(S_n\leq 0.4n) \leq \left[e^{0.4\lambda}(0.4+0.6e^{-\lambda})\right]^n, \qquad \lambda>0.

To minimize the expression inside brackets, differentiate its logarithm:

\frac{d}{d\lambda} \left[0.4\lambda+\log(0.4+0.6e^{-\lambda})\right] =0.4-\frac{0.6e^{-\lambda}}{0.4+0.6e^{-\lambda}}.

Setting the derivative to zero gives $0.4(0.4+0.6e^{-\lambda})=0.6e^{-\lambda}$, hence $0.16=0.36e^{-\lambda}$, so $e^{-\lambda}=4/9$ and $\lambda=\log(9/4)>0$. Substitution gives

e^{0.4\lambda}(0.4+0.6e^{-\lambda}) =\left(\frac94\right)^{0.4} \left(0.4+0.6\frac49\right) =\left(\frac94\right)^{0.4}\frac23 \approx 0.9221.

Therefore $P(S_n\leq0.4n)\leq(0.9221)^n$. The parameter is in the required positive domain, and the base is less than one, so the bound decays with $n$.

Worked Example: A Lower Tail for an Exponential Sum

Let $X_1,\ldots,X_n$ be independent exponential random variables with rate $2$, so each has mean $1/2$. Bound the probability that their sum is at most $n/4$.

The density is $f(x)=2e^{-2x}$ for $x\geq0$. For $\lambda\geq0$,

L(\lambda)=\int_0^\infty e^{-\lambda x}2e^{-2x}\,dx =2\int_0^\infty e^{-(2+\lambda)x}\,dx =\frac{2}{2+\lambda}.

The lower-tail bound is $[e^{\lambda/4}2/(2+\lambda)]^n$. Its logarithm per summand is $\lambda/4+\log 2-\log(2+\lambda)$, whose derivative is $1/4-1/(2+\lambda)$. The derivative vanishes at $\lambda=2$, which is admissible; it is negative below 2 and positive above 2. Thus this is the minimum, and

P(S_n\leq n/4) \leq \left[e^{2/4}\frac{2}{2+2}\right]^n =\left(\frac{\sqrt e}{2}\right)^n \approx (0.8244)^n.

The mean of each summand is $1/2$, while the threshold is $1/4$, so this is a genuine lower deviation. The optimized bound has a base below one, as expected.

Worked Example: A Useful Parameter for a Discrete Sum

Let each $X_i$ equal 0, 1, or 2 with probabilities $1/4,1/2,1/4$, respectively, and let $S_4=X_1+\cdots+X_4$ for independent summands. Bound $P(S_4\leq2)$.

The mean of one summand is $0(1/4)+1(1/2)+2(1/4)=1$, so the total mean is 4 and the threshold 2 is lower. The Laplace transform is

L(\lambda)=\frac14+\frac12e^{-\lambda}+\frac14e^{-2\lambda} =\frac{(1+e^{-\lambda})^2}{4}.

The bound is $e^{2\lambda}L(\lambda)^4$. Its logarithmic derivative is $2-8e^{-\lambda}/(1+e^{-\lambda})$. Setting this equal to zero gives $e^{-\lambda}/(1+e^{-\lambda})=1/4$, hence $e^{-\lambda}=1/3$, or $\lambda=\log 3$. The derivative is negative below $\log 3$ and positive above it, so this parameter minimizes the bound. To obtain a positive parameter with an informative, though not optimized, bound, choose $\lambda=0.2$. Then

e^{0.4}L(0.2)^4 =e^{0.4}\left(\frac14+\frac12e^{-0.2}+\frac14e^{-0.4}\right)^4 \approx 1.4918(0.82695)^4 \approx 0.698.

Thus $P(S_4\leq2)\leq0.698$. The calculation illustrates that checking the threshold and the numerical value matters: the selected parameter gives a valid bound below one, while the derivative calculation shows it is not the minimizing positive parameter.

Parameter Checks and a Common Pitfall

A frequent error is to assume that every valid Chernoff bound is informative. For example, retain the same distribution as in the preceding example, but consider $S_4\leq4$ and choose $\lambda=0.2$. The bound is

e^{0.8}\left(\frac14+\frac12e^{-0.2}+\frac14e^{-0.4}\right)^4 \approx 2.2255(0.82695)^4 \approx 1.041.

This inequality is mathematically valid, but it is weaker than the trivial probability bound $P(S_4\leq4)\leq1$. Reporting it as a useful numerical bound—or miscalculating the product as a value below one—is a mistake. The correction is to check the full expression, including the factor $e^{\lambda a}$, and then compare the result with one.

Before using a lower-tail Chernoff bound, check each of the following:

The summands are nonnegative, and the event is written with the correct threshold $S_n\leq a$.
The parameter has the form $-\lambda$ in the exponential, with $\lambda>0$. The transform is $E[e^{-\lambda X}]$, not $E[e^{\lambda X}]$.
The factor outside the transform is $e^{\lambda a}$. Its sign is positive because the event implies $e^{-\lambda S_n}\geq e^{-\lambda a}$.
The resulting bound is checked numerically against one; a value greater than one is valid but uninformative.

Why the Method Is Useful

The lower-tail Chernoff method converts a probability about a sum into expectations of simple transforms. Independence then turns the transform of the sum into a product, and identical distributions turn that product into a power. When a threshold lies below the mean, a suitable negative exponential parameter can produce an exponentially decreasing bound as the sample size grows. The bound need not be sharp to be useful: it can quantify how quickly a lower deviation becomes unlikely without calculating the exact distribution of the sum.

The essential discipline is to separate validity from usefulness. Nonnegativity guarantees that every $\lambda\geq0$ has a finite Laplace transform, and every $\lambda>0$ gives a valid inequality. Choosing a parameter that makes the numerical bound small is a separate step, requiring the threshold, transform, and parameter domain to be checked together.

Check Your Understanding

Try these questions using the event transformation and parameter checks developed above.

For $S_n=\sum_{i=1}^n X_i$ and $\lambda>0$, explain why $S_n\leq a$ implies $e^{-\lambda S_n}\geq e^{-\lambda a}$.
Why is $E[e^{-\lambda X}]$ finite for every $\lambda\geq0$ when $X$ is nonnegative?
If $X_i$ are identically distributed with Laplace transform $L$, write the Chernoff bound for $P(S_n\leq nx)$.
For the rate-2 exponential example, verify that $\lambda=2$ is a minimizing positive parameter for the threshold $n/4$.
What should you conclude if a valid parameter choice yields a numerical upper bound of 1.08 for a probability?