The Exponential Markov Inequality

From a Tail Event to an Exponential Moment

A tail probability such as $P(X\ge t)$ can be difficult to calculate directly, especially when the distribution of $X$ is complicated. An alternative is to bound the indicator of the tail event by a nonnegative random variable whose expectation is easier to evaluate. Exponentials are useful for this purpose: for a positive parameter $\lambda$, the function $x\mapsto e^{\lambda x}$ increases with $x$, so values above $t$ produce exponentials at least as large as $e^{\lambda t}$.

Applying Markov’s inequality to that exponential transform gives the exponential Markov inequality. Its usefulness depends on two conditions that must not be omitted: the exponential parameter must be positive, and the corresponding exponential moment must be finite.

Definition: The moment-generating function of a random variable $X$, at a real number $\lambda$ for which the expectation is finite, is $$ M_X(\lambda)=E[e^{\lambda X}]. $$ For an upper-tail bound at threshold $t$, an admissible exponential parameter is a real number $\lambda>0$ such that $M_X(\lambda)<\infty$.

The Inequality and Its Proof

Markov’s inequality states that if $Y$ is nonnegative and $a>0$, then $P(Y\ge a)\le E[Y]/a$, provided $E[Y]$ is finite. To use it here, take $Y=e^{\lambda X}$. For $\lambda>0$, exponentiation preserves order: $X\ge t$ implies $e^{\lambda X}\ge e^{\lambda t}$.

Theorem (Exponential Markov inequality): Let $X$ be a real-valued random variable, let $t\in\mathbb R$, and let $\lambda>0$ satisfy $M_X(\lambda)<\infty$. Then $$ P(X\ge t)\le e^{-\lambda t}M_X(\lambda) = \exp(-\lambda t)E[e^{\lambda X}]. $$

Proof. Since $\lambda>0$, the event $\{X\ge t\}$ is contained in $\{e^{\lambda X}\ge e^{\lambda t}\}$. The threshold $e^{\lambda t}$ is strictly positive, even when $t$ is negative. Markov’s inequality applied to the nonnegative random variable $e^{\lambda X}$ therefore gives

P(X\ge t) \le P(e^{\lambda X}\ge e^{\lambda t}) \le \frac{E[e^{\lambda X}]}{e^{\lambda t}} =e^{-\lambda t}M_X(\lambda).

The expectation in the last expression is finite by assumption, so the bound is well-defined. $\square$

This is a family of bounds: each admissible positive $\lambda$ gives a valid inequality. The right-hand side need not be less than one, so a convenient reported bound is sometimes the smaller of one and that quantity. Selecting or optimizing $\lambda$ is a separate question; the theorem itself only requires that the chosen value be positive and have a finite moment-generating function.

Centering the Random Variable

For a variable with finite mean $\mu=E[X]$, it is often useful to express the threshold as a distance above the mean. Write $t=\mu+s$, where $s>0$. The exponential moment of the centered variable is

E[e^{\lambda(X-\mu)}] =e^{-\lambda\mu}M_X(\lambda).

Corollary: If $E[X]=\mu$, $s>0$, and $\lambda>0$ satisfies $E[e^{\lambda(X-\mu)}]<\infty$, then $$ P(X-\mu\ge s) \le e^{-\lambda s}E[e^{\lambda(X-\mu)}]. $$

Derivation. Apply the theorem to $X-\mu$, whose upper-tail event at $s$ is exactly $\{X\ge\mu+s\}$. Its moment-generating function at $\lambda$ is $E[e^{\lambda(X-\mu)}]$, giving the displayed bound. Equivalently, substituting $t=\mu+s$ in the theorem yields

e^{-\lambda(\mu+s)}M_X(\lambda) =e^{-\lambda s}e^{-\lambda\mu}M_X(\lambda) =e^{-\lambda s}E[e^{\lambda(X-\mu)}].

Centering makes clear which part of the bound concerns the distance into the tail and which part describes the distribution’s exponential moment. It does not, by itself, ensure that this moment is finite.

Worked Examples

Worked Example: A Normal Upper-Tail Bound

Let $X\sim N(3,4)$, so its mean is $3$ and its variance is $4$. Bound $P(X\ge 7)$ using the particular choice $\lambda=1/2$.

For a normal variable with mean $\mu$ and variance $\sigma^2$, completing the square in its density gives $M_X(\lambda)=\exp(\mu\lambda+\sigma^2\lambda^2/2)$ for every real $\lambda$. Thus, here,

$M_X(\lambda)=\exp(3\lambda+2\lambda^2)$, which is finite at $\lambda=1/2$. The exponential Markov inequality gives

P(X\ge 7) \le e^{-7(1/2)}\exp\left(3(1/2)+2(1/2)^2\right) =e^{-3.5}e^{2} =e^{-1.5} \approx 0.2231.

This is a valid upper bound obtained with the stated parameter. It is not asserted to be the best bound obtainable from the theorem; no optimization is needed to verify its validity.

Worked Example: A Bernoulli Variable

Let $X$ equal $1$ with probability $1/4$ and $0$ with probability $3/4$. Use $\lambda=\log 2$ to bound $P(X\ge 1/2)$.

Because $\log 2>0$, the sign condition holds. The exponential moment is a two-point expectation:

M_X(\log 2) =\frac{3}{4}e^0+\frac{1}{4}e^{\log 2} =\frac{3}{4}+\frac{1}{2} =\frac{5}{4}.

The threshold factor is $e^{-\lambda t}=e^{-(\log 2)/2}=1/\sqrt{2}$. Therefore

P(X\ge 1/2) \le \frac{1}{\sqrt{2}}\frac{5}{4} =\frac{5}{4\sqrt{2}} \approx 0.884.

In this example, $P(X\ge 1/2)=1/4$, since only the value $1$ reaches the threshold. The bound is much larger than the actual probability, but it is still correct: an upper bound need not be close to the quantity it bounds.

Worked Example: A Three-Point Distribution

Suppose $X$ takes the values $-1,1,3$ with probabilities $1/2,3/10,1/5$, respectively. Use $\lambda=\log 2$ to bound $P(X\ge 2)$.

The probabilities sum to $1/2+3/10+1/5=1$, and the chosen $\lambda$ is positive. Since $X$ has finite support, its exponential moment is finite. Calculate it directly:

M_X(\log 2) =\frac{1}{2}2^{-1}+\frac{3}{10}2^1+\frac{1}{5}2^3 =\frac{1}{4}+\frac{3}{5}+\frac{8}{5} =\frac{49}{20}.

At threshold $t=2$, the multiplier is $e^{-2\log 2}=1/4$. Hence

P(X\ge 2) \le \frac{1}{4}\frac{49}{20} =\frac{49}{80} =0.6125.

The event consists only of the outcome $X=3$, so its actual probability is $1/5=0.2$, which is indeed at most $0.6125$. This calculation also illustrates that outcomes below the threshold still contribute to the exponential moment.

Conditions, Interpretation, and Common Mistakes

The positive sign of $\lambda$ is essential to the upper-tail argument. If $\lambda<0$, then $x\mapsto e^{\lambda x}$ is decreasing: $X\ge t$ implies $e^{\lambda X}\le e^{\lambda t}$, not $e^{\lambda X}\ge e^{\lambda t}$. The same application of Markov’s inequality therefore does not produce the stated upper-tail bound. Negative exponential parameters can be useful for lower-tail questions, but that requires a separate statement with the event and threshold oriented correctly.

Finiteness is equally important. The expression $E[e^{\lambda X}]$ must be a finite expectation at the particular positive $\lambda$ used. Knowing that $E[X]$ or even some ordinary moments exist does not automatically establish this condition. If the exponential moment is infinite, the displayed right-hand side is not a finite probability bound. Determining the full set of parameter values for which the moment is finite is a distinct task.

Common pitfall: A tempting but incorrect argument is, “Markov’s inequality applies to $e^{\lambda X}$, so choose any $\lambda$ and conclude an upper-tail bound.” The correction is to check both parts of the argument: $\lambda$ must be positive so the exponential preserves the upper-tail order, and $E[e^{\lambda X}]$ must be finite. A calculation that omits either check has not established the claimed bound.

A second practical caution is that a valid bound can be uninformative. If $e^{-\lambda t}M_X(\lambda)>1$, the theorem remains true, but the elementary bound $P(X\ge t)\le 1$ is tighter. Conversely, a finite exponential moment can make the bound useful at thresholds where direct tail probabilities are difficult to calculate. The method converts information about the distribution’s exponential moment into a statement about the probability of an extreme observation.

For sums or other complicated random quantities, the same inequality applies once their exponential moment is known to be finite. Any simplification of that moment requires additional facts about the variables and their dependence; the inequality itself does not assume independence. Keeping these roles separate helps avoid treating an exponential-moment calculation as though it were part of Markov’s inequality.

Check Your Understanding

Use the hypotheses and event transformations in the theorem to answer each question.

State the conditions on $\lambda$ and $M_X(\lambda)$ needed to bound $P(X\ge t)$ by the exponential Markov inequality.
For $X\sim N(0,1)$, write the bound for $P(X\ge 2)$ using $\lambda=1/2$. Is the resulting right-hand side finite?
Why does the proof for an upper-tail bound not work unchanged when $\lambda<0$?
If $E[e^{\lambda X}]=\infty$ for a proposed positive $\lambda$, what condition of the theorem fails?
Does the exponential Markov inequality require $X$ to be nonnegative or the summands defining $X$ to be independent? Explain.