Chernoff Bounds for Independent Nonidentical Summands

Why Keep the Summands Separate?

A sum of independent random variables need not have identically distributed terms. In that setting, the exponential Markov inequality still gives a useful tail bound: independence makes the moment-generating function (MGF) of the sum a product of the individual MGFs. Keeping those factors separate preserves the differences among the summands and makes the bound directly computable from their distributions.

The procedure is to choose an exponential parameter, multiply the individual MGFs, and then optimize over the parameters for which they are finite. The optimization can have a finite solution, but it need not: the infimum can occur only as the parameter approaches the edge of its domain. Checking the domain and the optimization conditions is therefore part of the argument, not an optional numerical detail.

The Product-MGF Chernoff Bound

Definition: Let \(X_1,\ldots,X_n\) be independent random variables and let \(S=\sum_{i=1}^n X_i\). For each \(i\), write \(M_i(t)=E[\exp(tX_i)]\) on the set where this expectation is finite. The common MGF domain for the sum is \(D=\bigcap_{i=1}^n\{t:M_i(t)<\infty\}\). For \(t\in D\), the log-MGF of the sum is \(K(t)=\sum_{i=1}^n\log M_i(t)\).

Independence gives \(E[\exp(tS)]=\prod_{i=1}^n M_i(t)\) whenever all the factors are finite. The Chernoff parameter for an upper tail must satisfy \(t>0\); for a lower tail it must satisfy \(t<0\). Both signs must also lie in the common MGF domain.

Theorem: For \(a\in\mathbb{R}\), if \(t\in D\) and \(t>0\), then \(P(S\ge a)\le \exp(-ta)\prod_{i=1}^n M_i(t)\). Consequently, \(P(S\ge a)\le \inf_{t\in D,\ t>0}\exp(-ta)\prod_{i=1}^n M_i(t)\). For \(t\in D\) with \(t<0\), \(P(S\le a)\le \exp(-ta)\prod_{i=1}^n M_i(t)\), and taking the infimum over such \(t\) gives a lower-tail bound.

Proof. If \(t>0\), then \(S\ge a\) implies \(\exp(tS)\ge \exp(ta)\). Markov's inequality applied to the nonnegative random variable \(\exp(tS)\) yields

P(S\ge a)\le \frac{E[\exp(tS)]}{\exp(ta)} =\exp(-ta)\prod_{i=1}^n M_i(t).

The equality uses independence and finiteness of the MGFs at \(t\). Since the inequality holds for every admissible positive \(t\), it also holds with the infimum of the right-hand side. If \(t<0\), the event \(S\le a\) implies \(\exp(tS)\ge \exp(ta)\), so the same Markov argument gives the lower-tail assertion. \(\square\)

For a centered sum, let \(\mu_i=E[X_i]\) when these means exist and define \(Y_i=X_i-\mu_i\). Applying the theorem to \(\sum_i Y_i\) gives, for \(u>0\),

P\left(\sum_{i=1}^n(X_i-\mu_i)\ge u\right) \le \inf_{\substack{t>0\\t\in D_Y}} \exp\left(-tu+\sum_{i=1}^n\log E[\exp(t(X_i-\mu_i))]\right),

where \(D_Y\) is the common MGF domain of the centered variables. Centering each term does not make their distributions identical; it simply expresses the threshold as a deviation above the sum of the means.

How to Optimize the Bound

For the upper-tail bound at threshold \(a\), minimize its logarithm, \(K(t)-ta\), over admissible \(t>0\). Suppose the individual MGFs are finite on an open interval containing the candidate \(t\), and are differentiable there. Then

\frac{d}{dt}\{K(t)-ta\} =\sum_{i=1}^n\frac{M_i'(t)}{M_i(t)}-a.

Thus an interior stationary point satisfies \(\sum_i M_i'(t)/M_i(t)=a\). It is a global minimizer on the admissible interval because \(K\) is convex there. To see the convexity, Hölder's inequality implies that each log-MGF \(t\mapsto\log E[\exp(tX_i)]\) is convex wherever the MGF is finite; sums of convex functions are convex. This condition identifies an interior optimizer when one exists. It does not guarantee one: the minimum may instead be approached at a boundary.

Optimization rule: Form \(K(t)=\sum_i\log M_i(t)\), minimize \(K(t)-ta\) over the valid positive parameters, and check both the domain and the endpoint behavior. For centered deviations, replace \(K(t)\) by the sum of the centered log-MGFs and \(a\) by the deviation \(u\).

Worked Applications

Worked Example: Two Unequal Bernoulli Summands

Let \(X_1\sim\operatorname{Bernoulli}(0.2)\) and \(X_2\sim\operatorname{Bernoulli}(0.4)\), independently, and set \(S=X_1+X_2\). Find the optimized Chernoff bound for \(P(S\ge1)\).

For a Bernoulli variable with success probability \(p\), its MGF is \(1-p+pe^t\). Put \(y=e^t\), so the positive-parameter condition is \(y>1\). The product-MGF bound becomes

P(S\ge1)\le \inf_{y>1}\frac{(0.8+0.2y)(0.6+0.4y)}{y} =\inf_{y>1}\left(\frac{0.48}{y}+0.44+0.08y\right).

Differentiating with respect to \(y\) gives \(-0.48/y^2+0.08\). Setting this equal to zero yields \(y^2=6\), and \(y=\sqrt{6}\approx2.4495\) is in the allowed range. The derivative is negative for \(1<y<\sqrt{6}\) and positive for \(y>\sqrt{6}\), confirming a minimum. Therefore \(t=\log(\sqrt{6})\approx0.8959\), and the optimized bound is

\frac{0.48}{\sqrt{6}}+0.44+0.08\sqrt{6} \approx 0.8319.

As a check, the exact probability is \(P(S\ge1)=1-P(X_1=0,X_2=0)=1-(0.8)(0.6)=0.52\), below the valid bound \(0.8319\). The two MGF factors differ because the success probabilities differ.

Worked Example: Independent Poisson Summands

Let \(X_1,X_2,X_3\) be independent Poisson variables with respective means \(0.5,1.5,2\). Bound \(P(S\ge7)\), where \(S=X_1+X_2+X_3\).

A Poisson variable with mean \(\lambda\) has MGF \(\exp(\lambda(e^t-1))\). Multiplying the three MGFs gives

E[\exp(tS)] =\exp(0.5(e^t-1))\exp(1.5(e^t-1))\exp(2(e^t-1)) =\exp(4(e^t-1)).

The upper-tail log bound at threshold 7 is \(4(e^t-1)-7t\). Its derivative is \(4e^t-7\), which vanishes at \(e^t=7/4\). This gives the admissible positive optimizer \(t=\log(7/4)\). The second derivative \(4e^t\) is positive, so this point minimizes the convex objective. Hence

P(S\ge7)\le \exp\left(4\left(\frac74-1\right)-7\log\left(\frac74\right)\right) =\exp\left(3-7\log\left(\frac74\right)\right) \approx 0.3996.

Each summand has a different mean, yet the product is straightforward: the exponents add. The resulting bound depends on their total mean, but the derivation uses independence of the individual variables.

Worked Example: Normal Summands With Different Variances

Suppose \(X_1\sim N(1,1)\) and \(X_2\sim N(2,4)\) independently. Bound \(P(S\ge6)\), where \(S=X_1+X_2\).

For \(X\sim N(\mu,\sigma^2)\), \(M(t)=\exp(\mu t+\sigma^2t^2/2)\), finite for every real \(t\). Thus

E[\exp(tS)] =\exp(t+t^2/2)\exp(2t+2t^2) =\exp(3t+5t^2/2).

The log bound is \(3t+5t^2/2-6t=-3t+5t^2/2\). Its derivative \(-3+5t\) vanishes at \(t=3/5=0.6\), an admissible positive parameter; the second derivative is 5, so this is the minimum. Substitution gives

P(S\ge6)\le \exp\left(-3(0.6)+\frac52(0.6)^2\right) =\exp(-0.9)\approx0.4066.

The sum has mean 3 and variance 5, as is also reflected in its MGF. The bound is obtained from the separate MGFs without assuming equal variances or identical distributions.

Common Pitfalls and Interpretation

Using one MGF as if the summands were identically distributed. Independence gives \(\prod_i M_i(t)\), not \(M(t)^n\) unless all the individual MGFs are equal.
Optimizing outside the MGF domain. A formal stationary point is unusable if one or more individual MGFs are infinite there.
Assuming the derivative equation always has a finite solution. It may have no solution in the allowed interval; then inspect the objective at the interval's boundaries and take an infimum if necessary.
Confusing the bound with the tail probability. Optimizing makes this particular exponential Markov bound as small as possible; it does not generally make the bound equal to the exact probability.

The product formulation matters whenever independent contributions have different distributions, as in sums of nonidentical Bernoulli indicators or measurements with unequal normal variances. It lets the analysis use each summand's own MGF rather than replacing the model with an identical-distribution assumption. The optimization step then selects the strongest bound available within the exponential Markov method.

Check Your Understanding

Use the product-MGF method and check the admissible parameter domain in each problem.

For independent Bernoulli variables with success probabilities \(0.1\) and \(0.7\), write the product MGF of their sum.
Why must an upper-tail Chernoff parameter be positive, and what sign is used for a lower-tail bound?
For independent Poisson variables with means \(\lambda_1,\ldots,\lambda_n\), simplify the product MGF of their sum.
State the derivative equation for an interior optimizer of the upper-tail bound at threshold \(a\).
What should be checked if that derivative equation has no solution in the allowed parameter interval?