Chebyshev's Sum Inequality

For similarly sorted sequences, the mean of products beats the product of means.

The idea

Theorem (Chebyshev's sum inequality).

If $a_1 \le a_2 \le \cdots \le a_n$ and $b_1 \le b_2 \le \cdots \le b_n$, then $\frac{1}{n}\sum_{i=1}^{n} a_i b_i \;\ge\; \left(\frac{1}{n}\sum_{i=1}^{n} a_i\right)\!\left(\frac{1}{n}\sum_{i=1}^{n} b_i\right),$ with equality if and only if one of the two sequences is constant. If instead one sequence increases while the other decreases, the inequality reverses.

In words: for two sequences sorted the same way, the mean of the termwise products is at least the product of the means.

Everything about the inequality, its direction, its reversal and its equality case, is read off one identity.

Lemma.

For any two sequences $a_1, \ldots, a_n$ and $b_1, \ldots, b_n$, $2n\sum_i a_i b_i - 2\left(\sum_i a_i\right)\!\left(\sum_i b_i\right) = \sum_{i,j}(a_i - a_j)(b_i - b_j).$

The left side is $2n^{2}$ times the difference of the two sides of the inequality, so its sign decides the inequality. When both sequences increase, $a_i - a_j$ and $b_i - b_j$ have the same sign for every pair $i, j$, so every term on the right is nonnegative. When the sequences are sorted oppositely, every term is nonpositive, which reverses the inequality; and when one sequence is constant, every term is zero, which is the equality case.

The figure draws that sign fact as a pairing: two $a$-values $a_i$, $a_k$ are matched with two $b$-values $b_j$, $b_l$, once crossed and once un-crossed. Sorting both sequences the same way is what un-crosses every pair — each larger $a$ holds a larger $b$ — and that is why every product $(a_i - a_j)(b_i - b_j)$ comes out nonnegative.

Ways to work on it

• Walkthrough. The mean-of-products bound, and how opposite sorting flips it.
• Practice. Compare the two sides for a similarly-sorted pair.
• Hardest. Derive and check a consequence for power sums.

Not sure where to start? Take the ten-question placement test.