Rearrangement Inequality
The rearrangement inequality is a statement about the pairwise products of two sequences. It can be extended to Chebyshev's inequality, and illustrates the practical power of greedy algorithms.
Definition
The rearrangement inequality states that, for two sequences and , the inequalities
hold, where is any permutation of .
Proof
Consider a permutation such that is maximized. The desired result is that is the identity permutation: i.e. for all . Suppose for the sake of contradiction that is not the identity, and let be the smallest integer such that .
Since is the smallest such integer, this means that (as the numbers to are already assigned). Furthermore, there must exist a such that , as some number must be assigned to .
Now, since , it follows that . Similarly, since , it follows that . Therefore,
so the sum is not decreased by changing to . This implies that the identity permutation gives the maximum possible value of , as desired.
Strategies and Applications
The value of the rearrangement inequality lies chiefly in the fact that it formalizes one's intuition towards what amounts to a greedy algorithm. For instance, if one were presented with a large number of $20 bills, $10 bills, $5 bills, and $1 bills, with the instructions to take 4 of one type of bill, 3 of another, 2 of another, and 1 of the last, it is intuitively obvious that four $20 bills, three $10 bills, two $5 bills, and one $1 bill should be selected. Indeed, this is precisely the statement of the rearrangement inequality, applied to the sequences and .
Like the Chebyshev inequality, care must be taken to assure both sequences are similarly ordered. Common strategies include
- .
Cycling the variables is also a powerful technique, as this preserves some ordering. For instance,
Show that
for reals .
Assume without loss of generality that . By rearrangement,
which is precisely the desired inequality.
A similar strategy leads to another proof of the AM-GM inequality:
Show that
for positive reals .
Assume without loss of generality that . The rearrangement inequality tells us that
which implies that
Additionally, the rearrangement inequality tells us that
which implies that
so it suffices to show that , or . This argument is then repeated until it is left to prove that , which is self-evident.