Chebyshev Inequality

There at least two different mathematical statements that go under the name of Chebyshev Inequality (Pafnuty Chebyshev (1821-1894), a famous Russian mathematician.) One in the realm of Probability Theory is of fundamental importance, the other - the subject of the present page - is an extremely useful and powerful tool for solving olympiad-kind inequalities.

Note that the inequalities can be put into a more symmetric form, as a statement of the averages, e.g.,

$\displaystyle \frac{1}{n}\sum_{i=1}^{n}x_iy_{i}\ge\left(\frac{1}{n}\sum_{i=1}^{n}x_i\right)\left(\frac{1}{n}\sum_{i=1}^{n}y_i\right),$

for similarly ordered sequences.

Assume, the sequences are similarly ordered. The second cases follows from this by changing the signs of all the terms in one of the sequences. With a reference to the Rearrangement Inequality,

$ \displaystyle \sum_{i=1}^{n}x_iy_{i}\ge x_1y_1+x_2y_2+\ldots+x_ny_n\\ \displaystyle \sum_{i=1}^{n}x_iy_{i}\ge x_1y_2+x_2y_3+\ldots+x_ny_1\\ \displaystyle \sum_{i=1}^{n}x_iy_{i}\ge x_1y_3+x_2y_4+\ldots+x_ny_2\\ \displaystyle \sum_{i=1}^{n}x_iy_{i}\ge x_1y_4+x_2y_5+\ldots+x_ny_3\\ \cdots \\ \displaystyle \sum_{i=1}^{n}x_iy_{i}\ge x_1y_n+x_2y_1+\ldots+x_ny_{n-1}\\ $

What remains is to sum all these up.

$\displaystyle\begin{align} n\sum_{i=1}^{n}x_iy_{i} - \sum_{i=1}^{n}x_i\sum_{j=1}y_i &= \sum_{j=1}^{n}\sum_{i=1}^{n}x_iy_{i} - \sum_{i=1}^{n}x_i\sum_{j=1}^{n}y_j\\ &= \sum_{i=1}^{n}\sum_{j=1}^{n}x_jy_{j} - \sum_{i=1}^{n}\sum_{j=1}^{n}x_iy_j\\ &= \sum_{j=1}^{n}\sum_{i=1}^{n}x_iy_{i} - \sum_{j=1}^{n}\sum_{i=1}^{n}x_jy_i\\ &= \frac{1}{2}\sum_{j=1}^{n}\sum_{i=1}^{n}(x_iy_{i}+x_jy_{j} -x_jy_i-x_iy_j)\\ &= \frac{1}{2}\sum_{j=1}^{n}\sum_{i=1}^{n}(x_i-x_j)(y_{i}-y_j)\\ &\ge 0. \end{align}$

Since both sequences are monotone, the inequality becomes equality when all the products vanish. This happens when $(x_1-x_n)(y_1-y_n)$ vanishes, i.e., when at least one of the sequences is constant.

We may consider the sequence $\{x_i\}$ to be ordered and note that the sequences $\{x_i\}$ and $\displaystyle\{x_i^{n}\}\;$ are ordered similarly. Then by the Chebyshev inequality,

$\displaystyle\begin{align} \frac{1}{n}\sum_{i=1}^{n}x_{i}^{n+1} &\ge \frac{1}{n}\sum_{i=1}^{n}x_{i}^{n}\frac{1}{n}\sum_{i=1}^{n}x_i\\ &\ge\sqrt[n]{x_{1}^{n}x_{2}^{n}\cdots x_{n}^{n}}\sum_{i=1}^{n}x_i\\ &= x_1x_2\ldots x_n\cdot\frac{1}{n}\cdot (x_1+x_2+\ldots+x_n). \end{align}$

This is equivalent to the required inequality.

Note: the above can be shown directly with the Rearrangement Inequality.

Set $s=a+b+c\;$ and rewrite the inequality as

$\displaystyle\frac{a}{s-a}+\frac{b}{s-b}+\frac{c}{s-c}\ge\frac{3}{2}.$

Assuming $a,b,c$ ordered, the terms $s-a,s-b,s-c\;$ are oppositely ordered. Thus by the Chebyshev inequality

$\displaystyle \left(\frac{a}{s-a}+\frac{b}{s-b}+\frac{c}{s-c}\right)\left[(s-a)+(s-b)+(s-c)\right]\ge 3(a+b+c).$

Since $(s-a)+(s-b)+(s-c)=2s,\;$ this is equivalent to Nesbitt's inequality.

1. Kin-Yin Li, Chebyshev Inequality, Mathematical Excalibur, Volume 4, Number 3, January, 1999 - March, 1999
2. Yue Kwok Choy, Chebyshev Inequality
3. Samin Riasat, Basics of Olympiad Inequalities
4. IMOMath, Chebyshev Inequality. Chebyshev’s Inequality
5. G. H. Hardy, J. E. Littlewood, G. Polya, Inequalities, Cambridge University Press (2^nd edition)
6. A. Engel, Problem-Solving Strategies, Springer Verlag, 1998 1988.
7. Xu Jiagu, Lecture Notes on Mathematical Olympiad Courses, v 8, (For senior section, v 2), World Scientific, 2012
8. P. Zeitz, The Art and Craft of Problem Solving, John Wiley & Sons, 1999