Pair two lists of numbers and add the products. The total is largest when both lists are sorted the same way and smallest when they are sorted in opposite ways: this is the rearrangement inequality. Chebyshev's inequality compares the average of the products with the product of the averages, and it follows from the same idea.
about 25 min1 simulation1 practice question
Lesson 3 of 3Show all lessonsHide
Try the code and the simulations beside the lesson.
What you will be able to do
state and prove the rearrangement inequality by swapping pairs;
use it to prove inequalities such as a2+b2+c2≥ab+bc+ca;
state, prove and use Chebyshev's sum inequality.
Pairing prices and quantities
A shop sells three items at 10, 20 and 50 rupees, and you must buy 1, 2 and 3 of them, one count for each item. To spend the most, buy 3 of the dearest item: 10×1+20×2+50×3=200 rupees. To spend the least, reverse it: 10×3+20×2+50×1=120 rupees. Every other choice lies in between.
The rearrangement inequality
Let a1≤a2≤⋯≤an and b1≤b2≤⋯≤bn. For any order c1,…,cn of the numbers b1,…,bn,
So a swap never lowers the total. Repeated swaps sort the list into the same order as the ai, so the same-order total is the largest. The smallest is proved the same way.
Two panels of bars for the prices 10, 20 and 50 rupees and the quantities 1, 2 and 3. On the left, same order: price 10 with quantity 1, 20 with 2, 50 with 3, total 200 rupees. On the right, opposite order: 10 with 3, 20 with 2, 50 with 1, total 120 rupees. Each product is drawn as a rectangle whose width is the quantity and whose height is the price.
A first use
Show that a2+b2+c2≥ab+bc+ca for all real a, b, c.
Take the list (a,b,c) twice. Pairing it with itself in the same order gives a2+b2+c2. Pairing it with (b,c,a) is another order, so its total ab+bc+ca is not larger. Done.
The same idea gives a3+b3+c3≥a2b+b2c+c2a for positive numbers: pair (a2,b2,c2) with (a,b,c), which is sorted the same way.
Chebyshev's sum inequality
If a1≤⋯≤an and b1≤⋯≤bn (sorted the same way), then
na1b1+⋯+anbn≥na1+⋯+an⋅nb1+⋯+bn.
If the lists are sorted in opposite ways, the inequality turns round.
Proof. For every pair i,j the numbers ai−aj and bi−bj have the same sign, so (ai−aj)(bi−bj)≥0. Add this over all i and j. The total is 2n∑aibi−2(∑ai)(∑bi)≥0.
An example. For positive a,b,c, the lists (a,b,c) and (a2,b2,c2) are sorted the same way. So 3(a3+b3+c3)≥(a+b+c)(a2+b2+c2).
Nesbitt again. If a≥b≥c, then a+b≥a+c≥b+c, so the lists (a,b,c) and (b+c1,c+a1,a+b1) are sorted the same way. Chebyshev and AM-HM finish the proof.
Practise with new numbers
Try it in Python
The program tries every way to pair two lists, and prints the largest and the smallest totals with the pairings that give them.
Common mistakes
Pairing without sorting. The rule is about the order of both lists. Sort first.
Using Chebyshev with lists sorted opposite ways. Then the inequality turns round.
Forgetting the n1 factors. Chebyshev compares averages: n∑aibi≥∑ai∑bi.
Assuming positivity is needed. Rearrangement and Chebyshev hold for any real numbers, as long as the order is right.
Remember these
Same order gives the largest total, opposite order the smallest.
A swap of an out-of-order pair changes the total by (aj−ai)(ci−cj).
Chebyshev: n∑aibi≥∑ai∑bi for lists sorted the same way.
a2+b2+c2≥ab+bc+ca is the simplest rearrangement result.
Check yourself
Try each one on your own first. If you are stuck, open a hint. Then check with Show the answer.
Pair the numbers 2,5,9 with 1,4,7. What are the largest and smallest totals of products?
Use rearrangement to show x2+y2≥2xy.
Check Chebyshev for the lists (1,2,3) and (4,5,9).
The lists (1,2,3) and (9,5,4) are sorted in opposite ways. Which way does Chebyshev's inequality go?
A swap changes the total by (aj−ai)(ci−cj). Find this change for ai=2, aj=6, ci=8, cj=3.
References
Hardy, Littlewood and Pólya, Inequalities, Chapter 10, on the rearrangement of sequences.
Engel, Problem-Solving Strategies, Chapter 7, on the rearrangement and Chebyshev inequalities.
Enroll free in Cauchy-Schwarz, Rearrangement and Chebyshev
Every lesson is open to read. Enrolling also lets you:
Mark lessons done and carry on where you stopped.
Take the tests of this lesson and its course.
Count the course towards the certificate for its chapter.