# 8 Chebychev’s Theorem

## 8.1 Chebychev’s Theorem

In any finite set of numbers and for any real number $$h > 1$$, at least $$(1 - \frac{1}{h^2}) \cdot 100\%$$ of the numbers lie within $$h$$ standard deviations of the mean. In other words, they lie within the interval $$(\mu-h\cdot\sigma , \mu+h\cdot\sigma)$$.

Proof:

For a set $$\{x_1,x_2,\ldots,x_r,x_{r+1},\ldots,x_n\}$$ where, by choice of labeling, $$\{x_1,x_2,\ldots,x_r\}$$ lie outside of $$(\mu-h\cdot\sigma , \mu+h\cdot\sigma)$$. Also, $$\{x_{r+1},\ldots,x_n\}$$ are within the interval. Under these conditions we know

$|x_1-\mu| > h\sigma,\ |x_2-\mu| > h\sigma, \ldots,\ |x_r-\mu| > h\sigma$

Squaring gives

$(x_1-\mu)^2 > h^2\sigma^2,\ (x_2-\mu)^2 > h^2\sigma^2,\ldots,\ (x_r-\mu)^2 > h^2\sigma^2\\ \ \ \ \ \Rightarrow\sum\limits_{i=1}^{r}(x_1-\mu)^2 > \sum\limits_{i=1}^{r}h^2\sigma^2 = rh^2\sigma^2$

Since all $$(x_i-\mu)^2$$ must necessarily be positive,

$\begin{array}{rrcl} &\sum\limits_{i=1}^{r}(x_i-\mu)^2 &<& \sum\limits_{i=1}^{n}(x_i-\mu)^2 \\ \Rightarrow & rh^2\sigma^2 &<& \sum\limits_{i=1}^{n}(x_i-\mu)^2 \\ ^{[1]} \Rightarrow & rh^2\sigma^2 &<& n\sigma^2 \\ \Rightarrow & rh^2 &<& n \\ \Rightarrow & \frac{r}{n} &<& \frac{1}{h^2} \end{array}$

1. $$\sigma^2 = \frac{1}{n}\sum\limits_{i=1}^{n}(x_i-\mu)^2$$
$$\ \ \ \ \Rightarrow n\sigma^2 = \sum\limits_{i=1}^{n}(x_i-\mu)^2$$

and $$\frac{r}{n}$$ is the fraction of numbers outside $$(\mu-h\cdot\sigma , \mu+h\cdot\sigma)$$. By the law of complements, the fraction of numbers inside the interval is $$1 - \frac{r}{n}$$, which implies $$1 - \frac{r}{n} > 1 - \frac{1}{h^2}$$. Thus, more than $$(1-\frac{1}{h^2})\cdot 100\%$$ of the points lie within $$h$$ standard deviations of the mean, or within the interval $$(\mu-h\cdot\sigma , \mu+h\cdot\sigma)$$.

## 8.2 Alternate Proof of Chebychev’s Theorem

In any finite set of numbers and for any real number $$h>1$$, at least $$(1-\frac{1}{h^2})\cdot 100\%$$ of the numbers lie within $$h$$ standard deviations of the mean. In other words, they lie within the interval $$(\mu-h\cdot\sigma,\mu+h\cdot\sigma)$$.\

Proof:

The proof here is done for the discrete case, but is applicable also in the continuous case by replacing the summations with integrals (with integrals, the limits will be from $$-\infty$$ to $$\infty$$).

$\begin{array}{rrcl} & \sigma^2 &=& E(x-\mu)^2 \\ & &=& \sum\limits_{y=0}^{\infty}(y-\mu)^2p(y) \\ & &=& \sum\limits_{y=0}^{\mu-h\sigma}(y-\mu)^2p(y) + \sum\limits_{y=\mu-h\sigma+1}^{\mu+h\sigma-1}(y-\mu)^2p(y) + \sum\limits_{y=\mu+h\sigma}^{\infty}(y-\mu)^2p(y) \\ ^{[1]} \Rightarrow & \sigma^2 &\geq& \sum\limits_{y=0}^{\mu-h\sigma}(y-\mu)^2p(y) + \sum\limits_{y=\mu+h\sigma}^{\infty}(y-\mu)^2p(y)\\ \end{array}$

1. Since all the $$(y-\mu)^2$$ must be positive, removing the middle term will surely result in this inequality.

In both of these summations $$y$$ is outside the interval $$(\mu-h\cdot\sigma , \mu+h\cdot\sigma)$$, so

$\begin{array}{rrcl} & |y-\mu| &\geq& h\sigma \\ \Rightarrow & (y-\mu^2) &\geq& h^2\sigma^2 \\ \Rightarrow & \sigma^2 &\geq& \sum\limits_{y=0}^{\mu-h\sigma}h^2\sigma^2 \Pr(Y = y) + \sum\limits_{\mu+h\sigma}^{\infty}h^2\sigma^2 \Pr(Y = y) \\ \Rightarrow & \sigma^2 &\geq& h^2\sigma^2\Big[\sum\limits_{y=0}^{\mu-h\sigma} \Pr(Y = y) + \sum\limits_{\mu+h\sigma}^{\infty} \Pr(Y = y)\Big] \end{array}$

The first summation is the sum of all probabilities that $$y-\mu < h\sigma$$, i.e. $$P(y-\mu < h\sigma)$$. Likewise, the second summation is $$P(y-\mu > h\sigma)$$.

$\begin{array}{rrcl} \Rightarrow & \sigma^2 &\geq& h^2\sigma^2[P(y-\mu<h\sigma) + P(y-\mu>h\sigma)] \\ \Rightarrow & \sigma^2 &\geq& h^2\sigma^2[P(|y-\mu|>h\sigma)] \\ \Rightarrow & \frac{1}{h^2} &\geq& \Pr(|y-\mu|>h\sigma) \\ \Rightarrow & 1-\frac{1}{h^2} &\leq& \Pr(|y-\mu|>h\sigma) \end{array}$

## 8.3 Chebychev’s Theorem for Absolute Deviation

This theorem is provided by Brunette (Brunette 2003–2007b)

In any finite set of numbers, and for any real number $$h > 1$$, at least $$1 - \frac{1}{h}$$ of the numbers lie within $$h$$ absolute deviations of the mean, where the absolute deviation is defined $$Ab = \frac{1}{n}\sum\limits_{i=1}{n}|x_i-\bar x|$$. In other words, $$1-\frac{1}{h}$$ of the numbers are in the interval $$(\bar x-h\cdot Ab , \bar x+h\cdot Ab)$$.

Proof:

For a set $$\{x_1,x_2,\ldots,x_r,x_{r+1},\ldots,x_n\}$$ where, by choice of labeling, $$\{x_1,x_2,\ldots,x_r\}$$ lie outside of $$(\mu-h\cdot Ab , \mu+h\cdot Ab)$$. Also, $$\{x_{r+1},\ldots,x_n\}$$ are within the interval. Accordingly,

$h \cdot Ab \leq |x_1-\bar x| ,\ h \cdot Ab \leq |x_1-\bar x| ,\ldots ,\ h \cdot Ab \leq |x_1-\bar x|$

$\begin{array}{rrcl} \Rightarrow & r \cdot h \cdot Ab &\leq& \sum\limits_{i=1}^{r}|x_i-\bar x| \\ \Rightarrow & r \cdot h \cdot Ab &\leq& \sum\limits_{i=1}^{n}|x_i-\bar x| \\ ^{[1]} \Rightarrow & r \cdot h \cdot Ab &\leq& n \cdot Ab\\ \Rightarrow & \frac{r}{n} &\leq& \frac{1}{h}\\ \Rightarrow & -\frac{r}{n} &\geq& -\frac{1}{h}\\ \Rightarrow & 1-\frac{r}{n} &\geq& 1-\frac{1}{h} \end{array}$

1. $$Ab = \frac{1}{n}\sum\limits_{i=1}^{n}|x_i-\bar x|$$
$$\Rightarrow n \cdot Ab = \sum\limits_{i=1}^{n}|x_i-\bar x|$$

Now $$\frac{r}{n}$$ is the fraction of numbers outside the interval. So $$1-\frac{r}{n}$$ is the fraction of numbers within $$h$$ absolute deviations of the mean, or within the interval $$(\mu-h\cdot Ab , \mu+h\cdot Ab)$$.

### References

Brunette, John. 2003–2007b. “Chebychev’s Theorem for Absolute Deviation.” Lecture Notes.