Last modified on May 17th, 2024

chapter outline

 

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}}$

Markov’s Inequality

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}}}$

Chebyshev’s Inequality

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

Last modified on May 17th, 2024