# Markov and Chebyshev’s Inequality

Markov’s and Chebyshev’s inequalities provide bounds on the probability that a random variable deviates from its mean (expected value) by a certain value.

Markov’s inequality is used when the random variable is unknown or difficult to compute, whereas Chebyshev’s inequality applies where the distance of the random variable from its mean.

## Markov’s Inequality

It states that if ‘X’ is a positive random variable defined on a sample space ‘S’ and the expected value E[X] exists, then for any positive real number ‘a’ (a Є ℝ++),

${P( X\geq a) \leq \dfrac{E\left[ X\right] }{a}}$

### Proof

First, we will prove the inequality for discrete random variables.

By definition, ${E\left[ X\right] =\sum _{x}xP( X= x)}$

Now, let us split this sum into two parts, depending on whether x ≥ a.

${E\left[ X\right] =\sum _{x\geq a}xP( X= x) +\sum _{x <a}xP( X= x)}$

Since the first part of the sum is for x ≥ a,

${E\left[ X\right] \geq \sum _{x\geq a}aP( X= x) +0}$

⇒ ${E\left[ X\right] \geq \sum _{x\geq a}aP( X= x)}$

⇒ ${E\left[ X\right] \geq a\sum _{x\geq a}P( X= x)}$

⇒ ${E\left[ X\right] \geq aP( X\geq a)}$

⇒ ${P( X\geq a) \leq \dfrac{E\left[ X\right] }{a}}$

Similarly, now we will prove the inequality for continuous random variables by replacing the summation with the integration sign.

${E\left[ X\right] =\int ^{\infty }_{0}xf_{X}\left( x\right) dx}$ (Since X ≥ 0)

By splitting the integral for the range 0 ≤ a ≤ ∞, we get

${E\left[ X\right] =\int ^{a}_{0}xf_{X}\left( x\right) dx+\int ^{\infty }_{a}xf_{X}\left( x\right) dx}$

Since a ≥ 0, x ≥ 0 and fX(x) ≥ 0, then ${\int ^{a}_{0}xf_{X}\left( x\right) dx\geq 0}$

${E\left[ X\right] \geq \int ^{\infty }_{a}xf_{X}\left( x\right) dx}$

⇒ ${E\left[ X\right] \geq \int ^{\infty }_{a}af_{X}\left( x\right) dx}$ (since x ≥ a in the integral)

⇒ ${E\left[ X\right] \geq a\int ^{\infty }_{a}f_{X}\left( x\right) dx}$

⇒ ${E\left[ X\right] \geq aP( X\geq a)}$

⇒ ${P( X\geq a) \leq \dfrac{E\left[ X\right] }{a}}$

Thus, Markov’s inequality is proved.

Find the lower bound on the probability P(X < 55) for a random variable X whose expected value is E[X] = 11

Solution:

Using the complement of probability, we get
P(X < 55) = 1 – P(X ≥ 55)
Now, by Markov’s inequality formula,
P(X ≥ 55) ≤ ${\dfrac{E\left[ X\right] }{55}}$
⇒ P(X ≥ 55) ≤ ${\dfrac{11}{55}}$
⇒ P(X ≥ 55) ≤ ${\dfrac{1}{5}}$
On multiplying both sides by (-1),
-P(X ≥ 55) ≥ ${-\dfrac{1}{5}}$
On adding 1 to both sides, we get
1 – P(X ≥ 55) ≥ 1 – ${\dfrac{1}{5}}$
⇒ 1 – P(X ≥ 55) ≥ ${\dfrac{4}{5}}$
Thus, the lower bound is P(X < 55) ≥ ${\dfrac{4}{5}}$

## Chebyshev’s Inequality

It states that if ‘X’ is a random variable with finite mean E[X] (μ) and finite variance  Var[X] (σ2), then for any strictly positive real number ‘k’, where k Є ℝ++

${P( \left| X-E\left[ X\right] \right| \geq k) \leq \dfrac{Var\left[ X\right] }{k^{2}}}$

Similarly,

${P( \left| X-\mu \right| \geq k) \leq \dfrac{\sigma }{k^{2}}}$

### Proof

Since (X – μ)2 is a positive random variable, here we will use Markov’s inequality.

${P( \left( X-\mu \right) ^{2}\geq a) \leq \dfrac{E\left[ \left( X-\mu \right) ^{2}\right] }{a}}$

By setting a = k2, we get

${P( \left( x-\mu \right) ^{2}\geq k^{2}) \leq \dfrac{E\left[ \left( x-\mu \right) ^{2}\right] }{k^{2}}}$ …..(i)

Since (X – μ)2 ≥ k2, which implies |X – μ| ≥ k …..(ii)

Using (ii) in (i), we get

${P( \left| x-\mu \right| \geq k) \leq \dfrac{E\left[ \left( x-\mu \right) ^{2}\right] }{k^{2}}}$ …..(iii)

From the definition of variance, we know E[(X – μ)2] = Var[X] = σ2

Thus, from (iii) we get, ${P( \left| x-\mu \right| \geq k) \leq \dfrac{\sigma ^{2}}{k^{2}}}$

### Continuous Form

However, there is a Continuous Version of Chebyshev’s inequality, which states that if f and g are both non-increasing functions or both non-decreasing functions over the closed interval [0, 1], and both are integrable over the closed interval [0, 1], then

${\int ^{1}_{0}f\left( x\right) g\left( x\right) dx\geq \int ^{1}_{0}f\left( x\right) dx\int ^{1}_{0}g\left( x\right) dx}$

## Chebyshev’s Sum Inequality

Chebyshev’s sum inequality (Chebyshev’s order inequality) is an algebraic inequality for real numbers which states that:

If a1 ≥ a2 ≥ … ≥ an and b1 ≥ b2 ≥ … ≥ bn are real numbers, then

${\dfrac{1}{n}\sum ^{n}_{i=1}a_{i}b_{i}\geq \dfrac{1}{n}\sum ^{n}_{i=1}a_{i}\times \dfrac{1}{n}\sum ^{n}_{i=1}b_{i}\geq \dfrac{1}{n}\sum ^{n}_{i=1}a_{i}b_{n+1-i}}$

⇒ ${\dfrac{a_{1}b_{1}+a_{2}b_{2}+\ldots +a_{n}b_{n}}{n}\geq \dfrac{a_{1}+a_{2}+\ldots +a_{n}}{n}\times \dfrac{b_{1}+b_{2}+\ldots +b_{n}}{n}\geq \dfrac{a_{1}b_{n}+a_{2}b_{n-1}+\ldots +a_{n}b_{1}}{h}}$

Proof

By rearrangement,

${a_{1}b_{1}+a_{2}b_{2}+\ldots +a_{n}b_{n}\geq a_{1}b_{1}+a_{2}b_{2}+\ldots +a_{n}b_{n}\geq a_{1}b_{n}+a_{2}b_{n-1}+\ldots +a_{n}b_{1}}$

${a_{1}b_{1}+a_{2}b_{2}+\ldots +a_{n}b_{n}\geq a_{1}b_{2}+a_{2}b_{3}+\ldots +a_{n}b_{1}\geq a_{1}b_{n}+a_{2}b_{n-1}+\ldots +a_{n}b_{1}}$

${a_{1}b_{1}+a_{2}b_{2}+\ldots +a_{n}b_{n}\geq a_{1}b_{3}+a_{2}b_{4}+\ldots +a_{n}b_{2}\geq a_{1}b_{n}+a_{2}b_{n-1}+\ldots +a_{n}b_{1}}$

${a_{1}b_{1}+a_{2}b_{2}+\ldots +a_{n}b_{n}\geq a_{1}b_{n}+a_{2}b_{1}+\ldots +a_{n}b_{n-1}\geq a_{1}b_{n}+a_{2}b_{n-1}+\ldots +a_{n}b_{1}}$

Adding all these inequalities, we get

${\dfrac{a_{1}b_{1}+a_{2}b_{2}+\ldots +a_{n}b_{n}}{n}\geq \dfrac{a_{1}+a_{2}+\ldots +a_{n}}{n}\times \dfrac{b_{1}+b_{2}+\ldots +b_{n}}{n}\geq \dfrac{a_{1}b_{n}+a_{2}b_{n-1}+\ldots +a_{n}b_{1}}{h}}$

Thus, Chebyshev’s sum inequality is proved.

Find the upper bound to the probability P(X ≥ 5) if E[X] = 2 and Var[X] = 1.

Solution:

Here, P(X ≥ 5) = P(X – 2 ≥ 3)
Using the properties of probability, we get
P(X ≥ 5) ≤ P(X – 2 ≥ 3 or X – 2 ≤ -3)
⇒ P(X ≥ 5) ≤ P(|X – 2| ≥ 3)
⇒ P(X ≥ 5) ≤ P(|X – E[X]| ≥ 3)
By Chebyshev’s inequality formula,
P(|X – E[X]| ≥ 3) ≤ ${\dfrac{Var\left[ X\right] }{3^{2}}}$
⇒ P(|X – E[X]| ≥ 3) ≤ ${\dfrac{1}{9}}$
The upper bound to the probability P(X ≥ 5) is ${\dfrac{1}{9}}$

If p + q + r = 27 and u + v + w = 35, find the smallest possible value of pu + qv + rw.

Solution:

By Chebyshev’s inequality formula, we have
${\dfrac{pu+qv+rw}{3}\geq \dfrac{p+q+r}{3}\cdot \dfrac{u+v+w}{3}}$
⇒ ${\dfrac{pu+qv+rw}{3}\geq \dfrac{27}{3}\cdot \dfrac{35}{3}}$
⇒ ${\dfrac{pu+qv+rw}{3}\geq 105}$
Thus, the smallest value of pu + qv + rw is 105