If we have a random variable $X$ and any number $a$, what is the probability that $X \geq a$? If we know the mean of $X$, Markov’s inequality can give an upper bound on the probability that $X$.  As it turns out, this upper bound is rather loose, and it can be improved if we know the variance of $X$ in addition to its mean. This result is known as Chebyshev’s inequality after the name of the famous mathematician Pafnuty Lvovich Chebyshev. It was  first proved by his student Andrey Markov who provided a proof in 1884 in his PhD thesis (see wikipedia).

Chebyshev’s Inequality

Let $X$ be a random variable with mean $\mu$ and variance $\sigma^2$. Let $k>0$ be any positive number. We ask the following question: What is the probability that $X$ will assume a value which which will be $k\sigma$ away from its mean? Chebyshev’s inequality says,

$\Pr\left[|X-\mu|\geq k\sigma \right] \leq \frac{1}{k^2}$

Proof

From Markov’s inequality, we know that for the random variable $X$ with mean $\mu$,

$\Pr[|X| \geq a ] \leq \frac{E[|X|]}{a}$.

Now consider the random variable $Y = \left(X - \mu\right)^2$. The expected value of this variable is $E\left[(X-\mu)^2\right]$ which, by definition, is the variance of $X$. Therefore,

$E[Y] = \sigma^2$.

Also, since $|Y|=|(X-\mu)^2|= (X-\mu)^2=Y$, it follows that $E[|Y|]=E[Y]=\sigma^2$.

According to Markov’s inequality, the probability that $|Y| \geq (k\sigma)^2$ is

$\Pr\left[\left|Y\right|\geq (k\sigma)^2\right]\leq \frac{E\left[|Y\right|] }{ (k\sigma)^2}=\frac{\sigma^2}{(k\sigma)^2}=\frac{1}{k^2}$.

Putting $|Y|=Y=(X-\mu)^2$, the above inequality becomes

$\Pr\left[(X-\mu)^2\geq (k\sigma)^2\right]\leq\frac{1}{k^2}$.

Since $(X-\mu)^2\geq(k\sigma)^2$ occurs precisely when $|X-\mu| \geq k\sigma$, it follows that

$\Pr[|X-\mu|\geq k\sigma]=\Pr[(X-\mu)^2 \geq (k\sigma)^2 ]\leq \frac{1}{k^2}$.

Proved. $\square$

What is the use?

Suppose, the random variable $X$ takes values between 0 and 1 (inclusive), has mean 0.5, and variance $0.16$. We ask: what is the probability that $X$ assumes a value $\geq 0.8$?

According to Markov’s inequality,

$\Pr[X \geq 0.8] \leq \frac{0.5}{0.8} = 0.625$.

However, according to Chebyshev’s inequality,

$\begin{array}{ccl}\Pr[X\geq 0.8]&=&\Pr[|X|\geq 0.8]\\&=&\Pr[|X-0.5|\geq 0.3]\\&=&\Pr[|X-0.5|\geq 0.16\times (\frac{0.3}{0.16})]\\&\leq & (\frac{0.16}{0.3})^2\\&\approx &0.284\end{array}$,

which is a much tighter bound.