Markov's Inequality and Tail Bounds

From an Indicator to a Tail Bound

A tail probability asks how likely a random variable is to reach or exceed a specified threshold. Knowing the whole probability law can make that probability computable, but often we know only an expectation or a moment. Markov’s inequality turns that limited information into a guaranteed upper bound. The bound may be conservative, but its hypotheses are simple, and the same argument leads directly to Chebyshev’s inequality.

Throughout, $(\Omega,\mathcal{F},\mathbb{P})$ is a probability space, so $\mathbb{P}(\Omega)=1$. A random variable $X$ here is a measurable real-valued function on this space. Expectations are Lebesgue integrals with respect to $\mathbb{P}$. We use the earlier results that expectation is monotone and that $\mathbb{E}[\chi_A]=\mathbb{P}(A)$ for $A\in\mathcal{F}$. An assertion holds almost surely if it holds outside a set of probability zero.

Theorem (Markov’s inequality): If $X$ is a nonnegative random variable almost surely, $0\le X<\infty$ almost surely, and $\mathbb{E}[X]<\infty$, then for every real $a>0$, $$ \mathbb{P}(X\ge a)\le\frac{\mathbb{E}[X]}{a}. $$ The same bound holds for $\mathbb{P}(X>a)$, since $\{X>a\}\subseteq\{X\ge a\}$.

Proof. For each $\omega\in\Omega$, if $X(\omega)\ge a$, then $\chi_{\{X\ge a\}}(\omega)=1\le X(\omega)/a$. If $X(\omega)<a$, the indicator is zero and $0\le X(\omega)/a$, since $X\ge0$ almost surely. Thus $\chi_{\{X\ge a\}}\le X/a$ almost surely. Monotonicity of expectation and the indicator expectation formula give $$ \mathbb{P}(X\ge a)=\mathbb{E}[\chi_{\{X\ge a\}}]\le\mathbb{E}[X/a]=\mathbb{E}[X]/a. $$ The last equality uses that $a$ is a positive finite constant. $\square$

The pointwise indicator comparison is the whole mechanism: on the event being measured, $X$ contributes at least $a$, so its expectation must be at least $a$ times the probability of that event. The assumption $a>0$ is essential to divide by the threshold. If $\mathbb{E}[X]=0$, the inequality says that every strictly positive threshold has zero upper-tail probability. If the expectation is infinite, a bound with right side $+\infty$ is valid but provides no information.

Worked Tail Bounds

Worked Example: A Discrete Tail Bound

Suppose $X$ takes the values $0,1,3,6$ with probabilities $1/2,1/4,1/6,1/12$, respectively. Find the exact probability that $X\ge3$, and compare it with Markov’s bound at $a=3$.

The probabilities sum to $$ \frac12+\frac14+\frac16+\frac1{12} =\frac6{12}+\frac3{12}+\frac2{12}+\frac1{12} =1, $$ so this specifies a probability law. Since $X$ is nonnegative and takes only finite values, it has finite expectation. Compute that expectation from the law: $$ \mathbb{E}[X] =0\cdot\frac12+1\cdot\frac14+3\cdot\frac16+6\cdot\frac1{12} =0+\frac14+\frac12+\frac12 =\frac54. $$ The event $X\ge3$ includes the values $3$ and $6$, so $$ \mathbb{P}(X\ge3)=\frac16+\frac1{12}=\frac14. $$ Markov’s inequality gives $\mathbb{P}(X\ge3)\le(5/4)/3=5/12$. Therefore the exact probability is at most the bound, since $1/4=3/12\le5/12$.

Check: the indicator bound on the two tail values is $1\le3/3$ at $X=3$ and $1\le6/3$ at $X=6$; off the tail, the indicator is zero. The expectation of $X/3$ is $(5/4)/3=5/12$, as in the inequality. Here the bound is not exact: $5/12-1/4=2/12=1/6$.

Worked Example: An Exponential Tail

Let $X$ have density $f(x)=e^{-x}$ for $x\ge0$ and $f(x)=0$ for $x<0$, with respect to Lebesgue measure on $\mathbb{R}$. Compute its tail at $2$ and compare it with Markov’s bound.

The density is nonnegative and integrates to $$ \int_0^\infty e^{-x}\,dx =\lim_{R\to\infty}(1-e^{-R})=1, $$ so it defines a probability law. The random variable is nonnegative almost surely. Its expectation is finite and equals $$ \mathbb{E}[X]=\int_0^\infty xe^{-x}\,dx=1. $$ For the last calculation, integration by parts on $[0,R]$ gives $\int_0^R xe^{-x}\,dx=1-(R+1)e^{-R}$, which tends to $1$ as $R\to\infty$. Thus Markov’s inequality applies with $a=2>0$, giving $\mathbb{P}(X\ge2)\le1/2$.

Direct integration gives the exact tail: $$ \mathbb{P}(X\ge2)=\int_2^\infty e^{-x}\,dx=e^{-2}. $$ This agrees with the bound because $e^{-2}<1/2$: equivalently, $e^2>2$. Check: the tail integral is $\lim_{R\to\infty}(e^{-2}-e^{-R})=e^{-2}$, while the expectation calculation above gives the bound $1/2$. The exact probability and the upper bound are distinct quantities.

Chebyshev’s Inequality

Markov’s inequality applies to nonnegative random variables. To control deviations of a general real-valued $X$ from its mean, apply it to the nonnegative squared deviation $(X-\mathbb{E}[X])^2$. Define the variance by $$ \operatorname{Var}(X)=\mathbb{E}\big[(X-\mathbb{E}[X])^2\big] $$ when $X$ has finite second moment. In particular, the mean is finite and the variance is finite in this setting.

Theorem (Chebyshev’s inequality): Let $X$ be a real-valued random variable on $(\Omega,\mathcal{F},\mathbb{P})$ with $\mathbb{E}[X^2]<\infty$, mean $\mu_X=\mathbb{E}[X]$, and variance $\sigma_X^2=\operatorname{Var}(X)$. For every $t>0$, $$ \mathbb{P}(|X-\mu_X|\ge t)\le\frac{\sigma_X^2}{t^2}. $$

Proof. Put $Y=(X-\mu_X)^2$. It is nonnegative and measurable. Since $\mathbb{E}[X^2]<\infty$, $Y$ has finite expectation, and $\mathbb{E}[Y]=\sigma_X^2$. Because $t>0$, the events $\{|X-\mu_X|\ge t\}$ and $\{Y\ge t^2\}$ are equal: squaring the nonnegative quantity $|X-\mu_X|$ preserves the inequality. Apply Markov’s inequality to $Y$ with positive threshold $t^2$. This gives $$ \mathbb{P}(|X-\mu_X|\ge t) =\mathbb{P}(Y\ge t^2) \le\frac{\mathbb{E}[Y]}{t^2} =\frac{\sigma_X^2}{t^2}. $$ The argument also covers $\sigma_X^2=0$; in that case the right side is zero for every $t>0$. $\square$

Worked Example: A Continuous Chebyshev Bound

Let $X$ be uniform on $[-2,2]$. Calculate its mean and variance, then compare the exact probability $\mathbb{P}(|X-\mathbb{E}[X]|\ge3/2)$ with Chebyshev’s bound.

The density is $1/4$ on $[-2,2]$ and zero elsewhere. Symmetry, or direct integration, gives $$ \mathbb{E}[X]=\frac14\int_{-2}^{2}x\,dx=0. $$ The second moment is $$ \mathbb{E}[X^2]=\frac14\int_{-2}^{2}x^2\,dx =\frac14\left(\frac{2^3}{3}-\frac{(-2)^3}{3}\right) =\frac14\cdot\frac{16}{3} =\frac43. $$ Thus $\operatorname{Var}(X)=\mathbb{E}[X^2]-(\mathbb{E}[X])^2=4/3$; the second moment is finite, so Chebyshev’s inequality applies.

With $t=3/2>0$, the exact event is $\{|X|\ge3/2\}$. Its two intervals, including their endpoints, are $[-2,-3/2]$ and $[3/2,2]$. Their total length is $1/2+1/2=1$, so the probability is $1/4$. Chebyshev’s bound is $$ \frac{\operatorname{Var}(X)}{t^2} =\frac{4/3}{(3/2)^2} =\frac{4/3}{9/4} =\frac{16}{27}. $$ The comparison is valid because $1/4=27/108\le64/108=16/27$. Check: the density assigns probability $1/4$ to a set of length $1$, and $ (3/2)^2=9/4$, giving the stated exact probability and bound.

What the Bounds Do—and Do Not—Say

Markov’s inequality uses only nonnegativity and the first moment; it does not require a density, independence, or a particular shape of the distribution. Chebyshev’s inequality uses the finite second moment and the variance, but does not require the random variable to be bounded or symmetric. In either case the result is an upper bound, not a formula for the tail probability. The examples show that the bound can exceed the exact probability, sometimes substantially.

A frequent error is to apply Markov’s inequality directly to a variable that can be negative. For example, let $X=2$ with probability $1/4$ and $X=-1$ with probability $3/4$. Then $\mathbb{E}[X]=2(1/4)-1(3/4)=-1/4$, but $\mathbb{P}(X\ge1)=1/4$. The incorrect calculation $1/4\le\mathbb{E}[X]/1=-1/4$ is false. The failure is not a defect in the inequality: the hypothesis $X\ge0$ almost surely was not met.

One valid repair for a one-sided event is to use the positive part $X^+=\max(X,0)$, which is nonnegative. In this example $X^+=2$ with probability $1/4$ and $0$ otherwise, so $\mathbb{E}[X^+]=2(1/4)=1/2$. Since $\{X\ge1\}\subseteq\{X^+\ge1\}$, Markov’s inequality gives $\mathbb{P}(X\ge1)\le\mathbb{E}[X^+]/1=1/2$, consistent with the exact probability $1/4$. For deviations around a mean, Chebyshev’s use of a square avoids this sign problem: the squared deviation is always nonnegative.

Pay attention to the event and threshold as well. The displayed versions bound events with a non-strict inequality, $\{X\ge a\}$ and $\{|X-\mu_X|\ge t\}$. Replacing either by its strict version gives a valid bound because the strict event is a subset of the displayed one. The thresholds must remain positive; at threshold zero, division by the threshold is undefined and these statements do not apply.

Check Your Understanding

For each question, check both the hypotheses and whether the event uses a strict or non-strict threshold.

If $X\ge0$ almost surely and $\mathbb{E}[X]=6$, what upper bound does Markov’s inequality give for $\mathbb{P}(X\ge4)$?
A nonnegative random variable has expectation $3/2$. What bound does Markov’s inequality give for $\mathbb{P}(X>6)$, and why is it valid for a strict tail?
If $\mathbb{E}[X]=2$ and $\operatorname{Var}(X)=9$, what does Chebyshev’s inequality give for $\mathbb{P}(|X-2|\ge6)$?
For a random variable that can be negative, explain why the pointwise comparison $\chi_{\{X\ge a\}}\le X/a$ may fail, even when $a>0$.
For the uniform random variable on $[-2,2]$, identify the event $\{|X|\ge3/2\}$ as intervals and compute its probability from the density.