Why Bound the Two Tails Separately?
For a centered sum, a large absolute deviation can occur in either direction. Exponential Markov bounds handle each direction by applying Markov’s inequality to a different nonnegative random variable: \(e^{\lambda S_n}\) for an upper deviation and \(e^{-\lambda S_n}\) for a lower one. These two moment-generating functions need not be equal. As a result, the strongest upper-tail and lower-tail bounds may use different parameters and have different sizes.
The goal here is to combine those separate bounds without assuming symmetry. We will also compare their result with Chebyshev’s inequality, which uses only the variance. Exponential bounds can decrease rapidly for large deviations, but they are not automatically tighter at every threshold.
Setup and Two One-Sided Bounds
Independence gives \(E[e^{\lambda S_n}]=M_Y(\lambda)^n\) whenever \(M_Y(\lambda)\) is finite. We require finiteness only at the parameter being used. For an upper-tail bound, the parameter is positive; for a lower-tail bound, we apply the same argument to \(-S_n\), which uses \(M_Y(-\lambda)\).
Proof. On the event \(S_n\ge t\), \(e^{\lambda S_n}\ge e^{\lambda t}\) for \(\lambda>0\). Markov’s inequality therefore gives $$ P(S_n\ge t) =P(e^{\lambda S_n}\ge e^{\lambda t}) \le e^{-\lambda t}E[e^{\lambda S_n}] =e^{-\lambda t}M_Y(\lambda)^n. $$ On \(S_n\le-t\), \(e^{-\lambda S_n}\ge e^{\lambda t}\), so the same argument yields $$ P(S_n\le-t) \le e^{-\lambda t}E[e^{-\lambda S_n}] =e^{-\lambda t}M_Y(-\lambda)^n. $$ The event \(\{|S_n|\ge t\}\) is the union of \(\{S_n\ge t\}\) and \(\{S_n\le-t\}\). Adding the two one-sided bounds gives a valid bound for any pair of admissible parameters. Taking the infimum separately for each side gives the stated result. \(\square\)
The parameters can be optimized separately because reducing one term does not require using the same parameter for the other. Equivalently, if the corresponding moment-generating functions are finite on the required parameter ranges, define $$ I_+(a)=\sup_{\lambda>0}\{\lambda a-\log M_Y(\lambda)\}, \qquad I_-(a)=\sup_{\lambda>0}\{\lambda a-\log M_Y(-\lambda)\}. $$ Then the separate bounds have the form \(P(S_n\ge t)\le e^{-nI_+(t/n)}\) and \(P(S_n\le-t)\le e^{-nI_-(t/n)}\). A supremum that is not attained still defines a valid infimum bound. The two rates can differ, even though the summands have mean zero.
Worked Example: A Normal Centered Sum
Suppose \(Y_1,\ldots,Y_n\) are independent with \(Y_i\sim N(0,\sigma^2)\), where \(\sigma^2>0\). Find the two-sided Chernoff bound and compare it with Chebyshev’s bound.
The normal moment-generating function is \(M_Y(\lambda)=e^{\sigma^2\lambda^2/2}\), which is finite for every real \(\lambda\). The upper-tail expression is $$ e^{-\lambda t}M_Y(\lambda)^n =\exp\left(-\lambda t+\frac{n\sigma^2\lambda^2}{2}\right). $$ Its exponent has derivative \(-t+n\sigma^2\lambda\), so its minimum over \(\lambda>0\) occurs at \(\lambda=t/(n\sigma^2)\). Substitution gives \(P(S_n\ge t)\le e^{-t^2/(2n\sigma^2)}\). Since \(M_Y(-\lambda)=M_Y(\lambda)\), the lower-tail bound is identical. Thus $$ P(|S_n|\ge t)\le 2e^{-t^2/(2n\sigma^2)}. $$
Here \(\operatorname{Var}(S_n)=n\sigma^2\), so Chebyshev’s inequality gives \(P(|S_n|\ge t)\le n\sigma^2/t^2\). At \(t=2\sigma\sqrt n\), the Chernoff bound is \(2e^{-2}\approx0.271\), while Chebyshev’s bound is \(1/4=0.25\); Chebyshev is slightly tighter. At \(t=3\sigma\sqrt n\), the bounds are \(2e^{-4.5}\approx0.0222\) and \(1/9\approx0.111\), respectively. The exponential bound is much tighter at this larger threshold.
Comparison with a Variance-Based Bound
A finite variance provides a two-sided bound even when the moment-generating function is unavailable. If \(\operatorname{Var}(Y_1)=\sigma^2<\infty\), independence and centering give \(\operatorname{Var}(S_n)=n\sigma^2\). Chebyshev’s inequality then implies $$ P(|S_n|\ge t)\le \frac{n\sigma^2}{t^2}. $$ Combining valid bounds yields the smaller of them, and probability itself is at most one: $$ P(|S_n|\ge t)\le \min\left\{1,\ \frac{n\sigma^2}{t^2},\ \inf_{\lambda>0}e^{-\lambda t}M_Y(\lambda)^n+ \inf_{\lambda>0}e^{-\lambda t}M_Y(-\lambda)^n\right\}, $$ where each infimum is restricted to parameters for which its moment-generating function is finite.
The variance bound follows by applying Markov’s inequality to \(S_n^2\): the event \(|S_n|\ge t\) implies \(S_n^2\ge t^2\), and \(E[S_n^2]=n\sigma^2\). This comparison has an important practical consequence: an exponential derivation does not guarantee a better numerical bound at every threshold. It may also return a number greater than one, in which case the bound \(P(|S_n|\ge t)\le1\) is more informative.
Worked Example: Separate Upper and Lower Bounds for a Bernoulli Sum
Let \(X_i\) be independent Bernoulli random variables with \(P(X_i=1)=0.2\), and set \(S_{10}=\sum_{i=1}^{10}(X_i-0.2)\). Bound \(P(|S_{10}|\ge2)\) by optimizing the two tails separately, then compare with Chebyshev’s inequality.
Write \(K=\sum_{i=1}^{10}X_i\), so \(S_{10}=K-2\). The upper event is \(K\ge4\), or \(K/10\ge0.4\); the lower event is \(K\le0\), or \(K/10\le0\). For a Bernoulli variable, \(M_Y(\lambda)=e^{-0.2\lambda}(0.8+0.2e^\lambda)\). More generally, optimizing the exponential bound for a binomial sum at a proportion \(q\) gives the exponent \(10D(q\Vert0.2)\), where $$ D(q\Vert p)=q\log\left(\frac{q}{p}\right)+(1-q)\log\left(\frac{1-q}{1-p}\right). $$ This expression follows by setting the derivative of \(\lambda q-\log(1-p+pe^\lambda)\) to zero; the optimizing value satisfies \(e^\lambda=q(1-p)/(p(1-q))\). For the lower tail the same calculation uses a negative parameter and gives the same expression with \(q<p\).
For the upper tail, \(q=0.4\), so $$ D(0.4\Vert0.2)=0.4\log 2+0.6\log(0.75)\approx0.10465, \qquad P(S_{10}\ge2)\le e^{-1.0465}\approx0.351. $$ For the lower tail, \(q=0\), so \(D(0\Vert0.2)=\log(1/0.8)\approx0.22314\). Therefore \(P(S_{10}\le-2)\le e^{-2.2314}=0.8^{10}\approx0.107\). Adding the two bounds gives \(P(|S_{10}|\ge2)\le0.351+0.107=0.458\).
The variance of each Bernoulli variable is \(0.2(0.8)=0.16\), so \(\operatorname{Var}(S_{10})=1.6\). Chebyshev gives \(P(|S_{10}|\ge2)\le1.6/4=0.4\), which is tighter than the combined Chernoff bound here. The lower tail is substantially smaller than the upper tail; applying the upper-tail result to both sides would lose that distinction.
Worked Example: A Rademacher Sum at a Large Threshold
Let \(Y_i\) independently equal \(1\) or \(-1\), each with probability \(1/2\). For \(S_{20}=\sum_{i=1}^{20}Y_i\), compare the two-sided Chernoff and Chebyshev bounds at \(t=12\).
Here \(M_Y(\lambda)=\cosh(\lambda)\), which is even. The two tails have equal bounds. For the upper tail, minimize \(-12\lambda+20\log\cosh(\lambda)\). Its derivative is \(-12+20\tanh(\lambda)\), which is zero when \(\tanh(\lambda)=0.6\). Thus \(\lambda=\operatorname{artanh}(0.6)=\frac12\log 4=\log2\).
Since \(\cosh(\log2)=(2+1/2)/2=1.25\), the one-sided bound is $$ e^{-12\log2}(1.25)^{20} =2^{-12}\left(\frac54\right)^{20} \approx e^{-3.8549}\approx0.0212. $$ The two-sided bound is therefore approximately \(2(0.0212)=0.0424\). The variance of \(S_{20}\) is \(20\), so Chebyshev gives \(20/12^2=20/144\approx0.139\). In this case, the Chernoff bound is substantially tighter.
Common Mistake and Practical Use
Common mistake: After deriving an upper-tail bound involving \(M_Y(\lambda)\), reuse it for the lower tail without changing the sign in the moment-generating function. The lower-tail event is controlled by \(e^{-\lambda S_n}\), so its bound involves \(M_Y(-\lambda)\), not \(M_Y(\lambda)\). These expressions agree when the centered summand has a symmetric distribution, but centering alone does not imply symmetry. The Bernoulli example shows the practical difference.
For a two-sided Chernoff calculation, first check which parameters have finite moment-generating functions, then optimize each side on its own admissible range. Add the resulting one-sided bounds, and compare their sum with both one and the Chebyshev bound when the variance is finite. This procedure uses exponential-tail information where it is available without discarding the baseline guarantee provided by the variance.
Check Your Understanding
Use the definitions and bounds above to answer the following questions.
- Why does the lower-tail bound for a centered sum involve \(M_Y(-\lambda)\) rather than \(M_Y(\lambda)\)?
- For independent centered summands, state the two one-sided Chernoff bounds for threshold \(t>0\).
- When can the upper-tail and lower-tail Chernoff bounds be equal for every positive parameter?
- If the two optimized Chernoff bounds sum to more than one, what valid bound can be reported instead?
- For the Rademacher example, which bound is smaller at \(t=12\), and what feature of the threshold helps explain the comparison?