Chebyshev's Inequality

Definition

For any random variable $X$ with a finite mean $\mu$ and a finite non-zero variance $\sigma^2$, Chebyshev's Inequality states that for any real number $k > 0$,

$$P(|{X} - \mu|\geq k\sigma)\leq \frac{1}{k^2}.$$

Proof

Let $Y$ be a random variable defined as $(X-\mu)^2$, hence $Y$ is a non-negative random variable.

Using Markov's inequality with any $k>0$

$$\begin{align*} P(Y \geq k^2\sigma^2)&\leq\frac{\mathbb{E}[Y]}{k^2\sigma^2}\\ P((X-\mu)^2 \geq k^2\sigma^2)&\leq\frac{\mathbb{E}[(X-\mu)^2]}{k^2\sigma^2}\\ P(|X-\mu| \geq k\sigma)&\leq\frac{\mathbb{Var}[X]}{k^2\sigma^2}\\ P(|X-\mu| \geq k\sigma)&\leq\frac{\sigma^2}{k^2\sigma^2}\\ P(|X-\mu| \geq k\sigma)&\leq\frac{1}{k^2}. \hspace{15px} \blacksquare\\ \end{align*}$$

Chebyshev's Inequality of the Sample mean

Definition

Let $X_i$ are i.i.d random variables with variance $\sigma^2$ and $\bar{X}_n:=\frac{1}{n}\sum_{i=1}^n X_i,$ then

$$P(|\bar{X}_n - \mathbb{E}[{X}]|\geq m)\leq \frac{\sigma^2}{m^2n}$$

for any $m>0$.

Proof

Some algebraic manipulations

$$\begin{align*} \mathbb{E}[\bar{X}_n]&=\frac{n\mathbb{E}[X]}{n}=\mathbb{E}[X],\\ \mathbb{Var}[\bar{X}_n]=\bar{\sigma}^2&=\mathbb{Var}\Big[\frac{1}{n}\sum_{i=1}^n X_i\Big]\\ &=\frac{1}{n^2}\mathbb{Var}\Big[\sum_{i=1}^n X_i\Big]\\ &=\frac{1}{n^2}\Big(\sum_{i=1}^n\mathbb{Var} [X_i]\Big)\hspace{20px}\text{(since } X_i's\text{ are i.i.d)}\\ &=\frac{\sigma^2}{n}\\ \sqrt{\mathbb{Var}[\bar{X}_n]}=\bar{\sigma}&=\frac{\sigma}{\sqrt{n}} \end{align*}$$

Since $\bar{X}_n$ is itself a random variable, Chebyshev's inequality can be written as

$$\begin{align*} P\Big(|\bar{X}_n - \mathbb{E}[\bar{X}_n]|\geq \underbrace{k\bar{\sigma}}_{m}\Big)\leq \frac{\bar{\sigma}^2}{k^2\bar{\sigma}^2}\\ P\Big(|\bar{X}_n - \mathbb{E}[{X}]|\geq m\Big)\leq \frac{{\sigma}^2}{m^2n}. \hspace{20px}\blacksquare\\ \end{align*}$$

Note: We will use Chebyshev's Inequality of the Sample mean to prove Weak law of large numbers.