Chebyshev's sum inequality explained

In mathematics, Chebyshev's sum 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{ 1 \over n} \sum ^{n} _{k =1} a _{k} b _{k} \geq \left({ 1 \over n}\sum ^{n} _{k =1} a _{k\right)\left({1} \over n}\sum ^{n} _{k =1} b _{k\right).}

Similarly, if

a _{1} \leq a _{2} \leq … \leq a _{n} and b _{1} \geq b _{2} \geq … \geq b _{n,} then{ 1 \over n} \sum ^{n} _{k =1} a _{k} b _{k} \leq \left({ 1 \over n}\sum ^{n} _{k =1} a _{k\right)\left({1} \over n}\sum ^{n} _{k =1} b _{k\right).} ^[1]

Proof

Consider the sum

S = \sum ^{n} _{j =1} \sum ^{n} _{k =1} (a _{j} - a _{k)} (b _{j} - b _{k).}

The two sequences are non-increasing, therefore and have the same sign for any . Hence .

Opening the brackets, we deduce:

0 \leq 2 n \sum ^{n} _{j =1} a _{j} b _{j} - 2 \sum ^{n} _{j =1} a _{j} \sum ^{n} _{j =1} b _{j,}

hence

(1)/(n) \sum ^{n} _{j =1} a _{j} b _{j} \geq \left( (1)/(n) \sum ^{n} _{j =1} a _{j\right)\left( (1)/(n)} \sum ^{n} _{j =1} b _{j\right).}

An alternative proof is simply obtained with the rearrangement inequality, writing that

\sum ^{n -1} _{i =0} a _{i} \sum ^{n -1} _{j =0} b _{j} = \sum ^{n -1} _{i =0} \sum ^{n -1} _{j =0} a _{i} b _{j} = \sum ^{n -1} _{i =0} \sum ^{n -1} _{k =0} a _{i} b _{i+k~mod~n} = \sum ^{n -1} _{k =0} \sum ^{n -1} _{i =0} a _{i} b _{i+k~mod~n} \leq \sum ^{n -1} _{k =0} \sum ^{n -1} _{i =0} a _{ib} _{i} = n \sum _{i} a _{ib} _{i.}

Continuous version

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

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

(1)/(b - a) \int ^{b} _{a} f(x)g(x) dx \geq \left( (1)/(b - a) \int ^{b} _{a} f(x) dx\right)\left( (1)/(b - a) \int ^{b} _{a} g(x) dx\right)

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

See also

• Hardy–Littlewood inequality
• Rearrangement inequality

Notes and References

1. Book: Hardy, G. H.. 0944909. Littlewood. J. E.. Pólya. G.. Inequalities. Cambridge Mathematical Library. Cambridge University Press. Cambridge. 1988. 0-521-35880-9.