Chebyshev’s Inequality

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.

Advertisements

One thought on “Chebyshev’s Inequality

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s