Misplaced Pages

Chebyshev's sum inequality

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.
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 ≥ a 2 ≥ ⋯ ≥ a n {\displaystyle a_{1}\geq a_{2}\geq \cdots \geq a_{n}\quad } and b 1 ≥ b 2 ≥ ⋯ ≥ b n , {\displaystyle \quad b_{1}\geq b_{2}\geq \cdots \geq b_{n},}

then

1 n ∑ k = 1 n a k b k ≥ ( 1 n ∑ k = 1 n a k ) ( 1 n ∑ k = 1 n b k ) . {\displaystyle {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 ≤ a 2 ≤ ⋯ ≤ a n {\displaystyle a_{1}\leq a_{2}\leq \cdots \leq a_{n}\quad } and b 1 ≤ b 2 ≤ ⋯ ≤ b n , {\displaystyle \quad b_{1}\leq b_{2}\leq \cdots \leq b_{n},}

then

1 n ∑ k = 1 n a k b k ≤ ( 1 n ∑ k = 1 n a k ) ( 1 n ∑ k = 1 n b k ) . {\displaystyle {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)\!.}

Proof

Consider the sum

S = ∑ j = 1 n ∑ k = 1 n ( a j − a k ) ( b j − b k ) . {\displaystyle S=\sum _{j=1}^{n}\sum _{k=1}^{n}(a_{j}-a_{k})(b_{j}-b_{k}).}

The two sequences are non-increasing, therefore aj − ak and bj − bk have the same sign for any j, k. Hence S ≥ 0.

Opening the brackets, we deduce:

0 ≤ 2 n ∑ j = 1 n a j b j − 2 ∑ j = 1 n a j ∑ j = 1 n b j , {\displaystyle 0\leq 2n\sum _{j=1}^{n}a_{j}b_{j}-2\sum _{j=1}^{n}a_{j}\,\sum _{j=1}^{n}b_{j},}

hence

1 n ∑ j = 1 n a j b j ≥ ( 1 n ∑ j = 1 n a j ) ( 1 n ∑ j = 1 n b j ) . {\displaystyle {\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_{j}\right)\!.}

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

∑ i = 0 n − 1 a i ∑ j = 0 n − 1 b j = ∑ i = 0 n − 1 ∑ j = 0 n − 1 a i b j = ∑ i = 0 n − 1 ∑ k = 0 n − 1 a i b i + k   mod   n = ∑ k = 0 n − 1 ∑ i = 0 n − 1 a i b i + k   mod   n ≤ ∑ k = 0 n − 1 ∑ i = 0 n − 1 a i b i = n ∑ i a i b i . {\displaystyle \sum _{i=0}^{n-1}a_{i}\sum _{j=0}^{n-1}b_{j}=\sum _{i=0}^{n-1}\sum _{j=0}^{n-1}a_{i}b_{j}=\sum _{i=0}^{n-1}\sum _{k=0}^{n-1}a_{i}b_{i+k~{\text{mod}}~n}=\sum _{k=0}^{n-1}\sum _{i=0}^{n-1}a_{i}b_{i+k~{\text{mod}}~n}\leq \sum _{k=0}^{n-1}\sum _{i=0}^{n-1}a_{i}b_{i}=n\sum _{i}a_{i}b_{i}.}

Continuous version

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

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

1 b − a ∫ a b f ( x ) g ( x ) d x ≥ ( 1 b − a ∫ a b f ( x ) d x ) ( 1 b − a ∫ a b g ( x ) d x ) {\displaystyle {\frac {1}{b-a}}\int _{a}^{b}f(x)g(x)\,dx\geq \!\left({\frac {1}{b-a}}\int _{a}^{b}f(x)\,dx\right)\!\!\left({\frac {1}{b-a}}\int _{a}^{b}g(x)\,dx\right)}

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

See also

Notes

  1. 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.
Categories: