From MGF Bounds to Explicit Concentration Tails

From an MGF Bound to a Tail Probability

A moment-generating function bound becomes useful for concentration when it is converted into a probability bound at a chosen deviation. The essential step is exponential Markov: for a positive parameter \(t\), a large value of a random variable forces its exponential to be large. The choice of \(t\) controls the resulting bound, so the strongest bound supplied by this method comes from optimizing over all permitted values.

This tutorial treats the conversion itself. It applies whether the MGF bound comes from an exact calculation or from a simpler upper envelope. The envelope need not be the exact MGF, but its range of validity matters: the optimization may use only parameter values for which the bound holds.

Definition: Let \(S\) be a centered random variable, so \(E[S]=0\), and suppose its MGF \(M_S(t)=E[e^{tS}]\) is finite for the parameter values under consideration. A function \(\psi\) is an MGF upper-bound function on a set \(D\) if \(M_S(t)\leq e^{\psi(t)}\) for every \(t\in D\). The corresponding log-MGF bound is \(\psi\); it need not equal \(\log M_S(t)\).

The One-Sided Conversion

For \(x>0\) and \(t>0\), the event \(\{S\geq x\}\) implies \(e^{tS}\geq e^{tx}\). Markov's inequality therefore gives \(P(S\geq x)\leq e^{-tx}E[e^{tS}]\). Substituting any valid MGF upper bound gives a family of bounds, one for each permitted \(t\).

Theorem: Suppose \(M_S(t)\leq e^{\psi(t)}\) for all \(t\) in a set \(D_+\subseteq(0,\infty)\). Then, for every \(x>0\),

$$ P(S\geq x)\leq \inf_{t\in D_+}\exp\{\psi(t)-tx\}. $$ If the infimum is not attained, this expression means the greatest lower bound of the bounds obtained over \(D_+\).

For the lower tail, apply the same argument to \(-S\). If the positive-parameter MGF of \(-S\) is bounded by \(e^{\psi_-(s)}\) for \(s\in D_-\subseteq(0,\infty)\), then

P(S\leq -x)\leq \inf_{s\in D_-}\exp\{\psi_-(s)-sx\}.

In terms of a bound on \(M_S(t)\) for negative \(t\), the lower-tail result uses \(t=-s<0\): the exponent is \(\psi(-s)-sx\). The separate notation \(\psi_-\) emphasizes that the useful bound on the negative side need not match the positive-side bound.

Proof: Fix \(t\in D_+\). Since \(e^{tS}\) is nonnegative and \(\{S\geq x\}\subseteq\{e^{tS}\geq e^{tx}\}\), Markov's inequality yields

P(S\geq x)\leq e^{-tx}E[e^{tS}] \leq \exp\{\psi(t)-tx\}.

This holds for every \(t\in D_+\), so taking the infimum proves the upper-tail statement. For the lower tail, apply the same reasoning to \(-S\): the event \(\{S\leq -x\}\) is \(\{-S\geq x\}\), and \(E[e^{s(-S)}]\leq e^{\psi_-(s)}\). Thus \(P(S\leq -x)\leq\exp\{\psi_-(s)-sx\}\) for every \(s\in D_-\), and taking the infimum proves the claim. \(\square\)

When \(S=\sum_{i=1}^n X_i\) for independent centered random variables and the individual MGFs are finite, independence gives \(M_S(t)=\prod_{i=1}^n M_{X_i}(t)\). Consequently, if \(M_{X_i}(t)\leq e^{\phi_i(t)}\) for each \(i\), then \(M_S(t)\leq e^{\sum_i\phi_i(t)}\) on the common range of validity. The theorem applies with \(\psi(t)=\sum_i\phi_i(t)\). This is how separate MGF bounds combine into a tail bound for a sum.

Optimizing the Parameter

Write the exponent to be minimized as \(\psi(t)-tx\). If \(\psi\) is differentiable and the minimum occurs at an interior point \(t_*>0\), differentiating gives the stationary-point equation \(\psi'(t_*)=x\). This equation identifies a candidate, not automatically a valid optimizer: one must check that \(t_*\) lies in the allowed domain and that it minimizes the exponent there. If the candidate lies outside the domain, the best available bound may instead come from a boundary or a limiting value.

Theorem: Suppose the positive-side bound holds for every \(t>0\) with \(\psi(t)=vt^2/2\), where \(v>0\). Then, for \(x>0\),

P(S\geq x)\leq e^{-x^2/(2v)}. $$ If the same MGF bound holds for \(M_S(-s)\) for every \(s>0\), then $$ P(|S|\geq x)\leq 2e^{-x^2/(2v)}.

Proof: The upper-tail exponent is \(vt^2/2-tx\). Its derivative is \(vt-x\), which vanishes at \(t_*=x/v>0\). Its second derivative is \(v>0\), so this point is the global minimum. Substitution gives \(v(x/v)^2/2-(x/v)x=-x^2/(2v)\), proving the one-sided bound. Applying the same calculation to \(-S\) gives \(P(S\leq -x)\leq e^{-x^2/(2v)}\). The event \(\{|S|\geq x\}\) is the union of \(\{S\geq x\}\) and \(\{S\leq -x\}\); adding their bounds proves the two-sided result. \(\square\)

Worked Examples

Worked Example: A Gaussian Sum

Let \(X_1,\ldots,X_n\) be independent, with \(X_i\sim N(0,\sigma_i^2)\), and set \(S=\sum_{i=1}^n X_i\). Find a two-sided bound for \(P(|S|\geq x)\), where \(x>0\).

For a centered Gaussian variable, \(E[e^{tX_i}]=e^{\sigma_i^2t^2/2}\). Independence therefore gives

M_S(t)=\prod_{i=1}^n e^{\sigma_i^2t^2/2} =e^{t^2\sum_{i=1}^n\sigma_i^2/2}.

Thus the quadratic bound holds in both directions with \(v=\sum_{i=1}^n\sigma_i^2\). The optimized one-sided bound is \(P(S\geq x)\leq e^{-x^2/(2v)}\), and the lower-tail bound is identical. Hence

P(|S|\geq x)\leq 2\exp\left\{-\frac{x^2}{2\sum_{i=1}^n\sigma_i^2}\right\}.

For example, if \(n=4\) and each variance is \(1\), then \(v=4\). At \(x=4\), the one-sided bound is \(e^{-16/8}=e^{-2}\), while the two-sided bound is \(2e^{-2}\), approximately \(0.271\). These are bounds, not claims that the tail probabilities equal those values.

Worked Example: A Rademacher Sum

Let \(X_1,\ldots,X_n\) be independent, with \(P(X_i=1)=P(X_i=-1)=1/2\), and let \(S=\sum_{i=1}^n X_i\). Derive a two-sided bound using an MGF upper bound.

For each summand, \(E[e^{tX_i}]=(e^t+e^{-t})/2=\cosh t\), so independence gives \(M_S(t)=(\cosh t)^n\). To bound this, let \(g(t)=\log\cosh t\). For \(t\geq0\), \(g(0)=0\) and \(g'(t)=\tanh t\leq t\): indeed, the derivative of \(t-\tanh t\) is \(1-\operatorname{sech}^2t=\tanh^2t\geq0\), and the difference is zero at \(0\). Integrating \(g'(t)\leq t\) from \(0\) to \(t\) gives \(g(t)\leq t^2/2\). Since \(g\) is even, this holds for negative \(t\) too. Therefore

M_S(t)\leq e^{nt^2/2}\qquad\text{for every real }t.

The quadratic result applies with \(v=n\), so

P(|S|\geq x)\leq 2e^{-x^2/(2n)}.

For \(n=100\) and \(x=20\), this is \(2e^{-400/200}=2e^{-2}\), approximately \(0.271\). The optimizing parameter on the upper side is \(t_*=x/n=0.2\); the lower-side calculation uses \(s_*=0.2\).

Worked Example: A Centered Poisson Sum

Let \(Y\sim\operatorname{Poisson}(\lambda)\) and \(S=Y-\lambda\). Derive an optimized upper-tail bound and evaluate it when \(\lambda=10\) and \(x=5\).

The Poisson MGF is \(E[e^{tY}]=\exp\{\lambda(e^t-1)\}\). Centering gives

M_S(t)=e^{-\lambda t}E[e^{tY}] =\exp\{\lambda(e^t-1-t)\}.

For \(x>0\), minimize \(\lambda(e^t-1-t)-tx\) over \(t>0\). The derivative is \(\lambda(e^t-1)-x\), which vanishes at \(t_*=\log(1+x/\lambda)>0\); the second derivative is \(\lambda e^t>0\), so this is the global minimum. Substitution yields

P(S\geq x)\leq \exp\left\{-\left[(\lambda+x)\log\left(1+\frac{x}{\lambda}\right)-x\right]\right\}.

For \(\lambda=10\) and \(x=5\), \(t_*=\log(1.5)\). The exponent in brackets is \(15\log(1.5)-5\), approximately \(1.08198\). Thus \(P(Y\geq15)\leq e^{-1.08198}\approx0.339\). The event threshold is \(Y\geq15\) because \(S=Y-10\); the bound need not be an integer threshold for the optimization, but this one happens to be.

Two-Sided Bounds and Their Interpretation

If upper- and lower-tail bounds are optimized separately, then for \(x>0\),

P(|S|\geq x) \leq \inf_{t\in D_+}e^{\psi_+(t)-tx} + \inf_{s\in D_-}e^{\psi_-(s)-sx}.

This follows from the union bound. The two optimized terms need not be equal: an asymmetric distribution, or an MGF estimate that is tighter on one side, can produce different upper- and lower-tail guarantees. If the resulting right-hand side exceeds \(1\), it remains a valid but uninformative probability bound; one may report its minimum with \(1\).

Common Pitfalls

Optimizing outside the valid range. If an MGF bound is established only for \(0<t<T\), a stationary point \(t_*\geq T\) cannot be substituted into it. Restrict the minimization to the valid range and check its boundary behavior.
Using the wrong sign for the lower tail. To bound \(P(S\leq-x)\), apply the upper-tail argument to \(-S\), or use a negative MGF parameter. Reusing the positive-side exponent without changing signs can produce an invalid expression.
Calling a sum of tails a two-sided one-tail bound. The factor of two in a symmetric bound comes from adding the upper and lower probabilities; it is not part of either one-sided calculation.
Treating an upper bound as an exact probability. Optimization finds the strongest bound within the chosen MGF method and envelope. It does not establish that the true tail attains that value.

Key takeaway: To turn an MGF estimate into a tail guarantee, write the exponential Markov bound, optimize only over the MGF bound’s valid domain, and handle the two tails separately before combining them.

Check Your Understanding

For each question, identify the parameter domain and show how it affects the claimed bound.

If \(M_S(t)\leq e^{vt^2/2}\) for all \(t>0\), what upper-tail bound follows, and which value of \(t\) optimizes it?
Why does a lower-tail bound for \(S\) involve the MGF of \(-S\), or equivalently a negative parameter in the MGF of \(S\)?
If the stationary point of \(\psi(t)-tx\) lies outside the domain where the MGF bound holds, what must be checked instead?
For independent centered variables with individual MGF bounds \(M_{X_i}(t)\leq e^{\phi_i(t)}\), what bound follows for the MGF of their sum?
Why can a valid two-sided bound exceed \(1\), and how should that affect its interpretation?