AoPSWiki
Visit the AoPS Book Store.
Personal tools

Chebyshev's Inequality

From AoPSWiki

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"
Want to learn how to tackle those tough AMC/AIME/Olympiad algebra problems? Check out Art of Problem Solving's Intermediate Algebra by Richard Rusczyk and Mathew Crawford. Over 1600 problems!
© Copyright 2008 AoPS Incorporated. All Rights Reserved. • Foundation • Privacy • Contact Us