Tchebysheff's theorem

Question

Let k≥1. Show that, for any set of n measurements, the fraction included in the interval $\bar{y} − ks$ to $\bar{y} + ks$ is at least $(1−1/k^2)$. This result is known as Tchebysheff's theorem.

Hint: $s^2=(1/(n−1))\displaystyle\sum\limits_{i=0}^n (y_i - \bar{y})^2$. In this expression, replace all deviations for which $|y_i − \bar{y}| \geq ks$ with ks. Simplify.

Can someone tell me where I am suppose to start with this problem? We haven't covered probabilities yet so no proofs with them.

Your formula for $s$ gives $s = 0$ since $\sum_i y_i = n\bar{y} = \sum_i \bar{y}$. — Dilip Sarwate, Sep 02 '13 at 01:31

achille hui · Accepted Answer · 2013-09-02T03:10:23.990

2

The "Hint" in your question is really the key to answer the question.

Assume the contrary. If the fraction of $|y_i - \bar{y}| \ge ks$ is greater than or equal to $\frac{1}{k^2}$, their part of contribution in $s^2$: $$\frac{1}{n-1}\sum_{\stackrel{i=1}{|y_i - \bar{y}| \ge ks}}^n (y_i - \bar{y})^2 \ge \frac{1}{n-1}\frac{n}{k^2} (ks)^2 = \frac{n}{n-1} s^2 > s^2 $$ is bigger than $s^2$ itself. This is absurd!

edited Sep 02 '13 at 03:10

answered Sep 02 '13 at 02:21

achille hui

122,701

why did you use $1/k^2$? – Username Unknown Sep 02 '13 at 02:36
@DramaFreak This is because Chebyshev's proved the theorem for $1 - 1/k^2$. In any event, $1 - 1/k^2$ is a better bound. If you really want, you can deduce the $1 - 1/k$ bound from that. – achille hui Sep 02 '13 at 02:52
Where did you get the $n/k^2$ in the second part of the inequality? – Username Unknown Sep 02 '13 at 02:55
@DramaFreak There are $n$ samples. If $1/k^2$ fraction of that has derivation $\ge ks$, there are at least $n/k^2$ samples contribution to that part of the sum. – achille hui Sep 02 '13 at 02:58

Tchebysheff's theorem

1 Answers1