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 f_X(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.

Chebyshev’s Inequality

It states that if ‘X’ is a random variable with finite mean E[X] (μ) and finite variance  Var[X] (σ²), 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 – μ)² 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 = k², 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 – μ)² ≥ k², 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 – μ)²] = Var[X] = σ²

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 a₁ ≥ a₂ ≥ … ≥ a_n and b₁ ≥ b₂ ≥ … ≥ b_n 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.