Exponential and Gamma Tail Bounds

Why These Distributions Make Useful Tail-Bound Examples

Exponential and gamma distributions are natural settings for seeing how a moment-generating function (MGF) turns a distributional formula into an upper-tail bound. The exponential distribution has one rate parameter; the gamma distribution adds a shape parameter and includes sums of independent exponential waiting times as an important special case. In both, the MGF is finite only up to a boundary. A successful calculation must respect that boundary as well as optimize the bound.

We use the rate parameterization: $\lambda>0$ is a rate, not a scale. Thus an exponential variable with rate $\lambda$ has mean $1/\lambda$, and a gamma variable with shape $\alpha$ and rate $\lambda$ has mean $\alpha/\lambda$. The focus here is the upper tail $P(X\ge x)$.

MGFs and Their Domains

Definition: An exponential random variable with rate $\lambda>0$, written $X\sim\operatorname{Exp}(\lambda)$, has density $f(x)=\lambda e^{-\lambda x}$ for $x\ge 0$. A gamma random variable with shape $\alpha>0$ and rate $\lambda>0$, written $X\sim\operatorname{Gamma}(\alpha,\lambda)$, has density $$ f(x)=\frac{\lambda^\alpha}{\Gamma(\alpha)}x^{\alpha-1}e^{-\lambda x},\qquad x>0, $$ where $\Gamma(\alpha)=\int_0^\infty u^{\alpha-1}e^{-u}\,du$.

The exponential distribution is the gamma distribution with shape $\alpha=1$. The distinction between rate and scale matters: the rate appears in the exponential factor $e^{-\lambda x}$.

For either density, the MGF is $M_X(t)=E[e^{tX}]$, when this expectation is finite. Substituting the gamma density and combining the exponential terms gives

M_X(t)=\frac{\lambda^\alpha}{\Gamma(\alpha)} \int_0^\infty x^{\alpha-1}e^{-(\lambda-t)x}\,dx.

If $t<\lambda$, the substitution $u=(\lambda-t)x$ evaluates the integral. If $t\ge\lambda$, its integrand has no exponential decay at infinity, and the integral diverges. This gives the MGF and its entire domain:

Result: If $X\sim\operatorname{Gamma}(\alpha,\lambda)$, then $$ M_X(t)=\left(\frac{\lambda}{\lambda-t}\right)^\alpha,\qquad t<\lambda. $$ For $t\ge\lambda$, $M_X(t)=\infty$. In particular, for $X\sim\operatorname{Exp}(\lambda)$, $M_X(t)=\lambda/(\lambda-t)$ for $t<\lambda$, and it is infinite for $t\ge\lambda$.

For completeness, the divergence at the boundary includes $t=\lambda$: the integrand is then proportional to $x^{\alpha-1}$, whose integral over $(0,\infty)$ diverges for every $\alpha>0$. For $t>\lambda$, the factor $e^{(t-\lambda)x}$ grows exponentially, so the integral also diverges.

Worked Example: Checking the MGF Domain

Let $X\sim\operatorname{Gamma}(2,3)$. Determine whether its MGF is finite at $t=2$, $t=3$, and $t=4$, and calculate it where it is finite.

The MGF exists exactly when $t<\lambda=3$. Therefore $t=2$ is allowed, and $$ M_X(2)=\left(\frac{3}{3-2}\right)^2=9. $$ At $t=3$, the denominator is zero and the defining integral diverges; the MGF is not finite there. At $t=4$, $t$ exceeds the rate and the integrand grows exponentially, so the MGF is again infinite. A formula involving $\lambda/(\lambda-t)$ cannot be used as a finite MGF outside its stated domain.

Optimizing the Upper-Tail Bound

The exponential Markov inequality says that if $Y\ge0$ and $a>0$, then $P(Y\ge a)\le E[Y]/a$. For $t\ge0$, apply it to $Y=e^{tX}$. When $X\ge x$, $e^{tX}\ge e^{tx}$; consequently, for any $t$ with $0\le t<\lambda$,

P(X\ge x)\le e^{-tx}M_X(t) =e^{-tx}\left(\frac{\lambda}{\lambda-t}\right)^\alpha.

The choice $t=0$ gives the valid but uninformative bound $1$. For $t>0$, the bound can be improved by choosing $t$ to minimize its right-hand side. The mean $\alpha/\lambda$ determines whether a positive optimizing value is useful.

Theorem: If $X\sim\operatorname{Gamma}(\alpha,\lambda)$, with $\alpha,\lambda>0$, then for $x>0$, $$ P(X\ge x)\le \begin{cases} 1, & 0<x\le \alpha/\lambda,\\[4pt] \exp(-\lambda x+\alpha)\left(\dfrac{\lambda x}{\alpha}\right)^\alpha, & x>\alpha/\lambda. \end{cases} $$ For $x>\alpha/\lambda$, the optimizing parameter is $t^*=\lambda-\alpha/x$, which lies in the valid range $0<t^*<\lambda$.

Proof. For $0\le t<\lambda$, take logarithms of the positive bound: $$ g(t)=-tx+\alpha\log\left(\frac{\lambda}{\lambda-t}\right). $$ Its derivatives are $$ g'(t)=-x+\frac{\alpha}{\lambda-t}, \qquad g''(t)=\frac{\alpha}{(\lambda-t)^2}>0. $$ Thus $g$ is strictly convex on its domain. If $x\le\alpha/\lambda$, then $g'(0)=-x+\alpha/\lambda\ge0$. Since $g'$ is increasing, $g$ is minimized over $0\le t<\lambda$ at $t=0$, giving the bound $e^{g(0)}=1$.

If $x>\alpha/\lambda$, then $g'(0)<0$, while $g'(t)$ tends to $+\infty$ as $t$ increases to $\lambda$. The unique zero of $g'$ is $$ t^*=\lambda-\frac{\alpha}{x}. $$ The assumption $x>\alpha/\lambda$ ensures $t^*>0$; also $\alpha/x>0$, so $t^*<\lambda$. Strict convexity makes this the global minimum. Substitution yields $$ e^{g(t^*)} =e^{-(\lambda-\alpha/x)x} \left(\frac{\lambda}{\alpha/x}\right)^\alpha =\exp(-\lambda x+\alpha)\left(\frac{\lambda x}{\alpha}\right)^\alpha. $$ This proves both cases. $\square$

The optimizing parameter can also be read as the balance between the penalty $e^{-tx}$ and the growth of the MGF as $t$ approaches its domain boundary. A larger threshold permits a choice closer to $\lambda$, but the boundary itself is never an admissible choice.

Worked Example: An Exponential Upper-Tail Bound

Let $X\sim\operatorname{Exp}(2)$. Bound $P(X\ge1)$ by optimizing over valid MGF parameters.

Here $\alpha=1$, $\lambda=2$, and the mean is $1/2$. Since $1>1/2$, the positive optimizer is $$ t^*=2-\frac{1}{1}=1, $$ which satisfies $0\le t^*<2$. The optimized bound is $$ P(X\ge1)\le e^{-1}\frac{2}{2-1}=\frac{2}{e}\approx0.7358. $$ For comparison, the exact exponential tail is $P(X\ge1)=e^{-2}\approx0.1353$. The inequality is valid but not exact: optimizing within this one-parameter family of bounds does not guarantee that the bound equals the actual tail probability.

Worked Example: A Gamma Upper-Tail Bound

Let $X\sim\operatorname{Gamma}(3,2)$, and bound $P(X\ge3)$.

The mean is $\alpha/\lambda=3/2$, so the threshold $3$ is above the mean. The optimizer is $$ t^*=2-\frac{3}{3}=1. $$ It is valid because $0<1<2$. At this value, $M_X(1)=(2/(2-1))^3=8$, and hence $$ P(X\ge3)\le e^{-3}M_X(1)=8e^{-3}\approx0.3983. $$ Equivalently, the theorem gives $\exp(-6+3)(6/3)^3=e^{-3}\cdot8$, the same result.

Worked Example: A Noninteger Gamma Shape

Let $X\sim\operatorname{Gamma}(1/2,4)$, and bound $P(X\ge1)$. This example shows that the formula does not require an integer shape.

The mean is $(1/2)/4=1/8$, which is below the threshold. The optimizing parameter is $$ t^*=4-\frac{1/2}{1}=\frac{7}{2}, $$ and $0<7/2<4$, so the MGF is finite there. Its value is $$ M_X(7/2)=\left(\frac{4}{4-7/2}\right)^{1/2} =\sqrt{8}. $$ Therefore $$ P(X\ge1)\le e^{-7/2}\sqrt{8}\approx0.0854. $$ The shape $1/2$ is positive, as required for the gamma density and MGF calculation.

Common Pitfall: Optimizing Outside the MGF Domain

A tempting but invalid step is to differentiate the bound and then accept any algebraic solution without checking its domain. For example, in the gamma calculation the stationary point is $t^*=\lambda-\alpha/x$. If $x\le\alpha/\lambda$, this value is nonpositive, so it does not provide a useful positive Chernoff parameter. The constrained minimum occurs at $t=0$, yielding only $1$.

Another error is to let $t$ reach or exceed $\lambda$ because a formal expression appears to offer a better value. At $t=\lambda$, however, the MGF is infinite; for $t>\lambda$, it is also infinite. The exponential Markov bound requires a finite expectation, so these choices cannot establish a tail bound. Always check both conditions: $t\ge0$ for this upper-tail argument and $t<\lambda$ for the gamma MGF.

Key takeaway: For an exponential or gamma variable, the MGF domain ends at the rate $\lambda$. Above the mean, the optimized upper-tail parameter is $t^*=\lambda-\alpha/x$, and the resulting bound is $\exp(-\lambda x+\alpha)(\lambda x/\alpha)^\alpha$. At or below the mean, this optimization gives only the trivial bound $1$.

Check Your Understanding

Work through each question, checking the MGF domain before optimizing.

For $X\sim\operatorname{Gamma}(4,2)$, state the full range of $t$ for which $M_X(t)$ is finite and calculate $M_X(1)$.
For $X\sim\operatorname{Exp}(3)$, find the optimizing parameter and the optimized upper-tail bound at threshold $x=1$.
For $X\sim\operatorname{Gamma}(2,5)$, explain why the optimized Chernoff bound at threshold $x=2/5$ is $1$.
For $X\sim\operatorname{Gamma}(2,1)$, calculate the optimizing parameter and the upper-tail bound at $x=4$.
Explain why setting $t=\lambda$ is not allowed when applying the exponential Markov inequality to a gamma variable.