AoPSWiki

Our Precalculus course starts on Dec. 4. Master trig, complex numbers, and vectors and matrices in 2 and 3 dimensions. Click here to enroll today!

Personal tools

Search

Toolbox

Chebyshev's Inequality

From AoPSWiki

Revision as of 19:15, 26 October 2007 by Temperal (Talk | contribs)

(diff) ← Older revision | Current revision (diff) | Newer revision → (diff)

Chebyshev's inequality, named after Pafnuty Chebyshev, states that if $a_1\geq a_2\geq ... \geq a_n$ and $b_1\geq b_2\geq ... \geq b_n$ then the following inequality holds:

$n \left(\sum_{i=1}^{n}a_ib_i\right)\geq\left(\sum_{i=1}^{n}a_i\right)\left(\sum_{i=1}^{n}b_i\right)$ .

On the other hand, if $a_1\geq a_2\geq ... \geq a_n$ and $b_n\geq b_{n-1}\geq ... \geq b_1$ then: $n \left(\sum_{i=1}^{n}a_ib_i\right)\leq\left(\sum_{i=1}^{n}a_i\right)\left(\sum_{i=1}^{n}b_i\right)$ .

Proof

Chebyshev's inequality is a consequence of the Rearrangement inequality, which gives us that the sum $S=a_1b_{i_1}+a_2b_{i_2}+...+a_nb_{i_n}$ is maximal when $i_k=k$ .

Now, by adding the inequalities:

$\sum_{i=1}^{n}a_ib_i\geq a_1b_1+a_2b_2+...+a_n b_{n}$ ,

$\sum_{i=1}^{n}a_ib_i\geq a_1b_2+a_2b_3+...+a_nb_1$ ,

...

$\sum_{i=1}^{n}a_ib_i\geq a_1b_n+a_2b_1+...+a_nb_{n-1}$

we get the initial inequality.

Retrieved from "http://www.artofproblemsolving.com/Wiki/index.php/Chebyshev%27s_Inequality"

Categories: Inequality | Theorems

Do you have what it takes to be the next brilliant trader, researcher, or developer at Jane Street Capital? Find out in the Careers in Mathematics Forum.

© Copyright 2008 AoPS Incorporated. All Rights Reserved. • Foundation • Privacy • Contact Us