Chebyshev's sum inequality

From Wikipedia, the free encyclopedia

For the similarly named inequality in probability theory, see Chebyshev's inequality.

In mathematics, Chebyshev's sum inequality, named after Pafnuty Chebyshev, states that if

$a_{1}\geq a_{2}\geq \cdots \geq a_{n}$

and

$b_{1}\geq b_{2}\geq \cdots \geq b_{n},$

then

${1 \over n}\sum _{{k=1}}^{n}a_{k}b_{k}\geq \left({1 \over n}\sum _{{k=1}}^{n}a_{k}\right)\left({1 \over n}\sum _{{k=1}}^{n}b_{k}\right).$

Similarly, if

$a_{1}\leq a_{2}\leq \cdots \leq a_{n}$

and

$b_{1}\geq b_{2}\geq \cdots \geq b_{n},$

then

${1 \over n}\sum _{{k=1}}^{n}a_{k}b_{k}\leq \left({1 \over n}\sum _{{k=1}}^{n}a_{k}\right)\left({1 \over n}\sum _{{k=1}}^{n}b_{k}\right).$ ^[1]

Proof

Consider the sum

$S=\sum _{{j=1}}^{n}\sum _{{k=1}}^{n}(a_{j}-a_{k})(b_{j}-b_{k}).$

The two sequences are non-increasing, therefore $a j - a k$ and $b j - b k$ have the same sign for any $j, k$ . Hence $S \geq 0$ .

Opening the brackets, we deduce:

$0\leq 2n\sum _{{j=1}}^{n}a_{j}b_{j}-2\sum _{{j=1}}^{n}a_{j}\,\sum _{{k=1}}^{n}b_{k},$

whence

${\frac {1}{n}}\sum _{{j=1}}^{n}a_{j}b_{j}\geq \left({\frac {1}{n}}\sum _{{j=1}}^{n}a_{j}\right)\,\left({\frac {1}{n}}\sum _{{j=1}}^{n}b_{k}\right).$

An alternative proof is simply obtained with the rearrangement inequality.

There is also a continuous version of Chebyshev's sum inequality:

If f and g are real-valued, integrable functions over [0,1], both non-increasing or both non-decreasing, then

$\int _{0}^{1}fg\geq \int _{0}^{1}f\int _{0}^{1}g,\,$

with the inequality reversed if one is non-increasing and the other is non-decreasing.

↑ Hardy, G. H.; Littlewood, J. E.; Pólya, G. (1988). Inequalities. Cambridge Mathematical Library. Cambridge: Cambridge University Press. ISBN 0-521-35880-9. MR 0944909.

This article is issued from Wikipedia. The text is available under the Creative Commons Attribution/Share Alike; additional terms may apply for the media files.