Optimizing the Chernoff Parameter

Turning the Chernoff Bound into an Optimization Problem

The exponential Markov inequality gives a family of upper bounds, one for each admissible positive parameter. The choice of parameter matters: a valid bound can still be much larger than another bound from the same family. Optimizing the parameter means finding the smallest bound that this method can provide, while respecting the moment-generating function's domain.

Let \(X\) be a real-valued random variable, let \(a\) be a real threshold, and define its moment-generating function by \(M(t)=E[e^{tX}]\) wherever this expectation is finite. For any \(t>0\) with \(M(t)<\infty\), the event \(\{X\ge a\}\) implies \(e^{tX}\ge e^{ta}\). Markov's inequality therefore gives

P(X\ge a)\le e^{-ta}M(t) =\exp\{g(t)-ta\},\qquad g(t)=\log M(t).

Thus the problem is to minimize the right-hand side over admissible \(t>0\). Since the exponential function is strictly increasing, this is equivalent to minimizing its logarithm

$$ h_a(t)=g(t)-ta. $$

The linear term \(-ta\) records the threshold, while \(g(t)\) records how rapidly the exponential moment grows. An interior optimum occurs when their slopes balance. But the positive parameter cannot always reach that balance: the infimum may instead be approached as \(t\) decreases to zero or as \(t\) approaches the edge of the MGF domain.

Why the Derivative of the Log MGF Controls the Choice

Definition: At an admissible parameter \(t\), the exponential Markov bound at threshold \(a\) is \(B_a(t)=\exp\{g(t)-ta\}\). Its log objective is \(h_a(t)=g(t)-ta\). A stationary parameter \(t_*>0\) satisfies \(g'(t_*)=a\).

Here is the regularity behind that derivative. Suppose \(M(t)\) is finite on an open interval containing \(t\). Then \(M\) is twice differentiable there, and

g'(t)=\frac{E[Xe^{tX}]}{E[e^{tX}]}, \qquad g''(t)=\frac{E[X^2e^{tX}]}{E[e^{tX}]} -\left(\frac{E[Xe^{tX}]}{E[e^{tX}]}\right)^2.

In particular, \(g''(t)\ge 0\). One way to see the meaning of these expressions is to define a probability distribution that weights outcomes in proportion to \(e^{tX}\): for any event \(A\), let \(P_t(A)=E[\mathbf{1}_A e^{tX}]/M(t)\). Then \(g'(t)\) is the expectation of \(X\) under this distribution and \(g''(t)\) is its variance. The derivative \(g'\) is therefore nondecreasing.

The differentiability claim needs more than merely a formal differentiation. Choose \(\varepsilon>0\) so that \(M(t-\varepsilon)\) and \(M(t+\varepsilon)\) are finite. For \(x\ge0\), \(|x|^k e^{tx}\) is bounded by a constant times \(e^{(t+\varepsilon)x}\); for \(x<0\), it is bounded by a constant times \(e^{(t-\varepsilon)x}\), for \(k=1,2\). These integrable bounds justify differentiating \(M\) twice under the expectation by dominated convergence. The displayed formulas then follow by differentiating \(g=\log M\). This argument applies at every interior point of the MGF's finite domain.

Theorem: Suppose \(M(t)<\infty\) on an open interval containing \(0\), and on a positive interval \((0,b)\), where \(0<b\le\infty\). Suppose \(g\) is differentiable on \((0,b)\), and write \(\alpha=g'(0)=E[X]\). Then \(h_a(t)=g(t)-ta\) is convex on \((0,b)\). If \(a>\alpha\) and there is a \(t_*\in(0,b)\) with \(g'(t_*)=a\), then \(t_*\) is a global minimizer over \((0,b)\). If \(g'\) is strictly increasing, it is the unique minimizer. If \(a\le\alpha\), the infimum over positive \(t\) is the limiting value \(h_a(0)=0\), so the corresponding bound approaches \(1\) as \(t\downarrow0\).

Proof. The differentiability argument above gives \(g''(t)\ge0\), so \(h_a''(t)=g''(t)\ge0\). Thus \(h_a\) is convex and \(h_a'(t)=g'(t)-a\) is nondecreasing. If \(g'(t_*)=a\), then \(h_a'(t_*)=0\). For \(t<t_*\), monotonicity gives \(h_a'(t)\le0\), and for \(t>t_*\), it gives \(h_a'(t)\ge0\). Hence \(h_a\) decreases up to \(t_*\) and increases after it; the stationary point is a global minimizer. If \(g'\) is strictly increasing, \(h_a'\) changes sign strictly, so no other minimizer exists.

If \(a\le\alpha\), monotonicity gives \(g'(t)\ge\alpha\ge a\) for every \(t>0\). Thus \(h_a'(t)\ge0\), and \(h_a\) is nondecreasing. Since \(M(0)=1\), we have \(h_a(t)\to h_a(0)=0\) as \(t\downarrow0\). The infimum is therefore \(0\), approached at the zero boundary; the corresponding bound approaches \(e^0=1\). The parameter \(t=0\) itself is not a positive Chernoff parameter. \(\square\)

When the derivative equation has no solution in \((0,b)\), the objective may keep decreasing across the whole admissible interval. Then the infimum is controlled by the right-hand boundary: it may be attained if that endpoint is admissible, or only approached if it is not. In particular, if \(b=\infty\), the best bound may be a limit as \(t\to\infty\), rather than a finite-parameter minimum.

Worked Optimizations

Worked Example: A Bernoulli Variable Has an Interior Optimum

Let \(X\sim\operatorname{Bernoulli}(0.3)\), so \(P(X=1)=0.3\) and \(P(X=0)=0.7\). Find the best exponential Markov bound for \(P(X\ge0.6)\) using positive \(t\).

The MGF is finite for every real \(t\):

M(t)=0.7+0.3e^t,\qquad g'(t)=\frac{0.3e^t}{0.7+0.3e^t}.

The mean is \(0.3\), below the threshold \(a=0.6\), so the zero-boundary case does not apply. Set \(g'(t)=0.6\) and solve:

\frac{0.3e^t}{0.7+0.3e^t}=0.6 \quad\Longrightarrow\quad 0.3e^t=0.42+0.18e^t \quad\Longrightarrow\quad e^t=3.5.

Thus \(t_*=\log(3.5)>0\), which is admissible. Substituting into the bound gives

B_{0.6}(t_*)=(0.7+0.3\cdot3.5)e^{-0.6\log(3.5)} =1.75\,(3.5)^{-0.6} \approx 0.825.

This is the smallest bound in the exponential Markov family. The actual probability is \(P(X\ge0.6)=0.3\), since the event is exactly \(\{X=1\}\). The optimized bound is valid but not exact.

Worked Example: A Normal Variable and a Threshold Above Its Mean

Let \(X\sim N(2,4)\), where the second parameter is the variance, and consider \(P(X\ge5)\). Find the minimizing parameter and bound.

For a normal variable with mean \(\mu\) and variance \(\sigma^2\), \(g(t)=\mu t+\sigma^2t^2/2\). Here,

g(t)=2t+2t^2,\qquad g'(t)=2+4t.

Equating the derivative to the threshold \(a=5\) gives \(2+4t=5\), so \(t_*=3/4\). Because \(t_*>0\) and the normal MGF is finite for every real \(t\), this is an admissible interior optimum. The log bound is

h_5(3/4)=2(3/4)+2(3/4)^2-5(3/4) =\frac{3}{2}+\frac{9}{8}-\frac{15}{4} =-\frac{9}{8}.

Therefore \(P(X\ge5)\le e^{-9/8}\approx0.325\). More generally, when \(a>\mu\), solving \(\mu+\sigma^2t=a\) gives \(t_*=(a-\mu)/\sigma^2\), and substitution yields the bound \(\exp\{-(a-\mu)^2/(2\sigma^2)\}\).

Worked Example: An Exponential Variable and the MGF-Domain Boundary

Let \(X\sim\operatorname{Exponential}(1)\), with density \(e^{-x}\) for \(x\ge0\), and find the best bound for \(P(X\ge3)\).

The MGF is finite only for \(t<1\), and for positive Chernoff parameters the admissible interval is \(0<t<1\):

M(t)=\int_0^\infty e^{tx}e^{-x}\,dx =\frac{1}{1-t},\qquad g(t)=-\log(1-t),\qquad g'(t)=\frac{1}{1-t}.

Solve \(g'(t)=3\): \(1/(1-t)=3\), hence \(t_*=2/3\). This lies strictly inside the admissible interval. The minimized log bound and bound are

h_3(2/3)=-\log(1/3)-2 =\log 3-2, \qquad B_3(2/3)=3e^{-2}\approx0.406.

The endpoint \(t=1\) cannot be used because the MGF is infinite there. In this case the derivative equation has a valid interior solution, so there is no need to optimize at the domain boundary.

Boundary Cases and a Common Mistake

The behavior at the left boundary has a useful interpretation. If \(E[X]\) is finite and \(a\le E[X]\), then the log objective cannot decrease as \(t\) moves right from zero. The resulting infimum \(1\) gives no improvement over the elementary probability bound \(P(X\ge a)\le1\). A useful exponential Markov bound generally requires a threshold above the mean, though being above the mean alone does not guarantee an interior solution: the derivative must also reach the threshold within the admissible MGF domain.

For example, return to \(X\sim\operatorname{Bernoulli}(0.3)\), but take \(a=1.2\). Now \(g'(t)=0.3e^t/(0.7+0.3e^t)<1\) for every finite \(t\), so the equation \(g'(t)=1.2\) has no solution. The objective is decreasing, and as \(t\to\infty\),

h_{1.2}(t)=\log(0.7+0.3e^t)-1.2t \longrightarrow -\infty.

Consequently the bound approaches zero. This is consistent with \(P(X\ge1.2)=0\), because \(X\le1\). The infimum is not attained at any finite \(t\).

Common mistake: solving \(g'(t)=a\) and reporting the result without checking whether it is positive and admissible. The equation may have no solution, or its solution may lie outside the MGF's finite domain. The correction is to check the domain first, examine the derivative across that domain, and compare with the relevant boundary behavior. A stationary point is a candidate optimum only when it is actually admissible.

Key takeaway: Minimize the log bound \(h_a(t)=g(t)-ta\). When an admissible positive solution of \(g'(t)=a\) exists, convexity makes it a global minimizer. Otherwise, determine whether the best bound is approached at zero or at the edge of the MGF domain.

Check Your Understanding

Use the derivative of the log MGF and check the admissible parameter range in each problem.

Why does minimizing \(\exp\{g(t)-ta\}\) give the same minimizing parameter as minimizing \(g(t)-ta\)?
If \(g'(0)=E[X]\) and \(a<E[X]\), what happens to the log objective as \(t\) increases from zero?
For \(X\sim N(\mu,\sigma^2)\) with \(a>\mu\), solve \(g'(t)=a\) and state the resulting bound.
For \(X\sim\operatorname{Exponential}(1)\), which positive values of \(t\) are admissible? Why can \(t=1\) not be used?
What should be checked if the equation \(g'(t)=a\) has no solution inside the positive MGF domain?