proof of Chebyshev’s inequality

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

$(x_1{y}_1+x_2{y}_2+\mathrm{\cdots }+x_n{y}_n)$ (1)

$+$ $(x_1{y}_2+x_2{y}_3+\mathrm{\cdots }+x_{n-1}{y}_n+x_n{y}_1)$

$+$ $(x_1{y}_3+x_2{y}_4+\mathrm{\cdots }+x_{n-2}{y}_n+x_{n-1}{y}_1+x_n{y}_2)$

$+$ $\mathrm{\cdots }$

$+$ $(x_1{y}_n+x_2{y}_1+x_3{y}_2+\mathrm{\cdots }+x_n{y}_{n-1}).$

• If $y_1\le y_2\le \mathrm{\cdots }\le y_n$, each of the $n$ terms in parentheses is less than or equal to $x_1{y}_1+x_2{y}_2+\mathrm{\cdots }+x_n{y}_n$, according to the rearrangement inequality. From this, it follows that

  $$(x_1+x_2+\mathrm{\cdots }+x_n)(y_1+y_2+\mathrm{\cdots }+y_n)\le n(x_1{y}_1+x_2{y}_2+\mathrm{\cdots }+x_n{y}_n)$$

  or (dividing by $n^2$)

  $$\left(\frac{x_1+x_2+\mathrm{\cdots }+x_n}{n}\right)\left(\frac{y_1+y_2+\mathrm{\cdots }+y_n}{n}\right)\le \frac{x_1{y}_1+x_2{y}_2+\mathrm{\cdots }+x_n{y}_n}{n}.$$

• If $y_1\ge y_2\ge \mathrm{\cdots }\ge y_n$, the same reasoning gives

  $$\left(\frac{x_1+x_2+\mathrm{\cdots }+x_n}{n}\right)\left(\frac{y_1+y_2+\mathrm{\cdots }+y_n}{n}\right)\ge \frac{x_1{y}_1+x_2{y}_2+\mathrm{\cdots }+x_n{y}_n}{n}.$$

It is clear that equality holds if $x_1=x_2=\mathrm{\cdots }=x_n$ or $y_1=y_2=\mathrm{\cdots }=y_n$. To see that this condition is also necessary, suppose that not all $y_i$’s are equal, so that $y_1\ne y_n$. Then the second term in parentheses of (1) can only be equal to $x_1{y}_1+x_2{y}_2+\mathrm{\cdots }+x_n{y}_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_1{y}_1+x_2{y}_2+\mathrm{\cdots }+x_n{y}_n$ if $x_1=x_2$. This implies that $x_1=x_2=\mathrm{\cdots }=x_n$. Therefore, Chebyshev’s inequality is an equality if and only if $x_1=x_2=\mathrm{\cdots }=x_n$ or $y_1=y_2=\mathrm{\cdots }=y_n$.

Title	proof of Chebyshev’s inequality
Canonical name	ProofOfChebyshevsInequality
Date of creation	2013-03-22 13:08:38
Last modified on	2013-03-22 13:08:38
Owner	pbruin (1001)
Last modified by	pbruin (1001)
Numerical id	4
Author	pbruin (1001)
Entry type	Proof
Classification	msc 26D15