PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
sections
Encyclopædia
Papers
Books
Expositions

meta
Requests (230)
Orphanage
Unclass'd
Unproven (519)
Corrections (16)
Classification

talkback
Polls
Forums
Feedback
Bug Reports

downloads
Snapshots
PM Book

information
News
Docs
Wiki
ChangeLog
TODO List
Legalese
About
Owner confidence rating: Medium Entry average rating: No information on entry rating
[parent] proof of Chebyshev's inequality (Proof)

Let $ x_1,x_2,\ldots,x_n$ and $ y_1,y_2,\ldots,y_n$ be real numbers such that $ x_1\le x_2\le\cdots\le x_n$. Write the product $ (x_1+x_2+\cdots+x_n)(y_1+y_2+\cdots+y_n)$ as

    $\displaystyle (x_1y_1+x_2y_2+\cdots+x_ny_n)$  
  $\displaystyle +$ $\displaystyle (x_1y_2+x_2y_3+\cdots+x_{n-1}y_n+x_ny_1)$  
  $\displaystyle +$ $\displaystyle (x_1y_3+x_2y_4+\cdots+x_{n-2}y_n+x_{n-1}y_1+x_ny_2)$  
  $\displaystyle +$ $\displaystyle \cdots$  
  $\displaystyle +$ $\displaystyle (x_1y_n+x_2y_1+x_3y_2+\cdots+x_ny_{n-1}).$ (1)

  • If $ y_1\le y_2\le\cdots\le y_n$, each of the $ n$ terms in parentheses is less than or equal to $ x_1y_1+x_2y_2+\cdots+x_ny_n$, according to the rearrangement inequality. From this, it follows that
    $\displaystyle (x_1+x_2+\cdots+x_n)(y_1+y_2+\cdots+y_n)\le n(x_1y_1+x_2y_2+\cdots+x_ny_n) $
    or (dividing by $ n^2$)
    $\displaystyle \left(\frac{x_1+x_2+\cdots+x_n}{n}\right) \left(\frac{y_1+y_2+\cdots+y_n}{n}\right)\le \frac{x_1y_1+x_2y_2+\cdots+x_ny_n}{n}. $
  • If $ y_1\ge y_2\ge\cdots\ge y_n$, the same reasoning gives
    $\displaystyle \left(\frac{x_1+x_2+\cdots+x_n}{n}\right) \left(\frac{y_1+y_2+\cdots+y_n}{n}\right)\ge \frac{x_1y_1+x_2y_2+\cdots+x_ny_n}{n}. $
It is clear that equality holds if $ x_1=x_2=\cdots=x_n$ or $ y_1=y_2=\cdots=y_n$. To see that this condition is also necessary, suppose that not all $ y_i$'s are equal, so that $ y_1\neq y_n$. Then the second term in parentheses of (1) can only be equal to $ x_1y_1+x_2y_2+\cdots+x_ny_n$ if $ x_{n-1}=x_n$, the third term only if $ x_{n-2}=x_{n-1}$, and so on, until the last term which can only be equal to $ x_1y_1+x_2y_2+\cdots+x_ny_n$ if $ x_1=x_2$. This implies that $ x_1=x_2=\cdots=x_n$. Therefore, Chebyshev's inequality is an equality if and only if $ x_1=x_2=\cdots=x_n$ or $ y_1=y_2=\cdots=y_n$.



"proof of Chebyshev's inequality" is owned by pbruin.
(view preamble)

View style:


This object's parent.
Log in to rate this entry.
(view current ratings)

Cross-references: Chebyshev's inequality, implies, necessary, equality, clear, rearrangement inequality, terms, product, real numbers

This is version 1 of proof of Chebyshev's inequality, born on 2002-11-10.
Object id is 3582, canonical name is ProofOfChebyshevsInequality2.
Accessed 5843 times total.

Classification:
AMS MSC: 26D15 (Real functions :: Inequalities :: Inequalities for sums, series and integrals)
Pending Errata and Addenda
None.
Discussion
Style: Expand: Order:
forum policy
Proof of Chebyshev's inequality by induction by TomLK on 2004-05-16 13:55:16

is much cleaner, and requires only the two term rearrangement inequality $(x_iy_i+x_jy_j\le x_iy_j+x_jy_i)$:

For n=1 we have equality.

Let $n\ge2$ and assume that $(x_1+\cdots+x_n)(y_1+\cdots+y_n)\le n(x_1y_1+\cdota+x_ny_n)$;

then

$[(x_1+\cdots+x_n)+x_{n+1}][(y_1+\cdots+y_n)+y_{n+1}]
=(x_1+\cdots+x_n)(y_1+\cdots+y_n)
+\sum_{k=1}^n(x_ky_{n+1}+x_{n+1}y_k)
+x_{n+1}y_{n+1}$;

on the right hand side

the first term is $\le n(x_1y_1+\cdots+x_ny_n)$
by assumption,

since $x_ky_{n+1}+x_{n+1}y_k\le x_ky_k+x_{n+1}y_{n+1}$,
the second term is $\le (x_1y_1+\cdots+x_ny_n)+nx_{n+1}y_{n+1}$;

together with the third term, this makes the right side
$\le (n+1)(x_1y_1+\cdots+x_{n+1}y_{n+1}), and the proof is complete. 

[ reply | up ]
Interact
post | correct | update request | add example | add (any)