Chebyshev's sum inequality

Another article treats Chebyshev's inequality in probability theory.

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_kb_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 \geq a_2 \geq \cdots \geq a_n$

and

$b_1 \leq b_2 \leq \cdots \leq b_n,$

then

${1\over n} \sum_{k=1}^n a_kb_k \leq \left({1\over n}\sum_{k=1}^n a_k\right)\left({1\over n}\sum_{k=1}^n b_k\right).$

[edit] Proof

Chebyshev's sum inequality follows from the rearrangement inequality.

Suppose we have

$a_1 \geq a_2 \geq \cdots \geq a_n \,$

and

$b_1 \geq b_2 \geq \cdots \geq b_n. \,$

Because of the rearrangement inequality we get that

$a_1 b_1 + \cdots + a_n b_n \,$

is the maximum value the arrangement of the arrangement of the two sequences.

$a_1 b_1 + \cdots + a_n b_n = a_1 b_1 + a_2 b_2 + \cdots + a_n b_n \,$

$a_1 b_1 + \cdots + a_n b_n \geq a_1 b_2 + a_2 b_3 + \cdots + a_n b_1 \,$

$a_1 b_1 + \cdots + a_n b_n \geq a_1 b_3 + a_2 b_4 + \cdots + a_n b_2 \,$

$\vdots \,$

$a_1 b_1 + \cdots + a_n b_n \geq a_1 b_n + a_2 b_1 + \cdots + a_n b_{n-1} \,$

By addition one gets

$n (a_1 b_1 + \cdots + a_n b_n) \geq (a_1 + \cdots + a_n) (b_1 + \cdots + b_n);$

dividing by $n 2$ :

$\frac {(a_1 b_1 + \cdots + a_n b_n)} {n} \geq \frac {(a_1 + \cdots + a_n)}{n} \cdot \frac {(b_1 + \cdots + b_n)}{n}.$

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

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

$\int fg \geq \int f \int g.\,$

This can be generalized to integrals over any space, as well as products of countable integrals.