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 \(a_1 \geq a_2 \geq \ldots \geq a_n\) and \(b_1 \geq b_2 \geq \ldots \geq b_n\), the inequality
\[a_1b_1+a_2b_2+\ldots+a_nb_n \geq a_1b_{\pi(1)}+a_2b_{\pi(2)}+\ldots+a_nb_{\pi(n)} \geq a_1b_n+a_2b_{n-1}+\ldots+a_nb_1\]
where \(\pi(1), \pi(2), \ldots, \pi(n)\) is any permutation of \(1, 2, \ldots, n\).
Proof
Consider a permutation \(\pi(1), \pi(2), \ldots, \pi(n)\) such that \(a_1b_{\pi(1)}+a_2b_{\pi(2)}+\ldots+a_nb_{\pi(n)}\) is maximized. The desired result is that \(\pi\) is the identity permutation; i.e. \(\pi(i)=i\) for all \(i\). Suppose for the sake of contradiction that \(\pi\) is not the identity, and let \(i\) be the smallest integer such that \(\pi(i) \neq i\).
Since \(i\) is the smallest such integer, this means that \(\pi(i)=j>i\) (as the numbers \(1\) to \(i-1\)) are already assigned. Furthermore, there must exists a \(k>i\) such that \(\pi(k)=i\), as some number must be assigned to \(i\).
Now, since \(i<j\), it follows that \(b_i \leq b_j\). Similarly, since \(i<k\), it follows that \(a_i \leq a_k\). Therefore \[0 \leq (a_k-a_i)(b_j-b_i) \implies a_ib_j+a_kb_i \leq a_kb_j+a_ib_i\] so the sum \(a_1b_{\pi(1)}+\ldots+a_nb_{\pi(n)}\) is not decreased by changing \(\pi(i)=j, \pi(k)=i\) to \(\pi(i)=i, \pi(k)=j\). This implies that the identity permutation gives the maximum possible value of \(a_1b_{\pi(1)}+a_2b_{\pi(2)}+\ldots+a_nb_{\pi(n)}\), 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 \(20, 10, 5, 1\) and \(4, 3, 2, 1\).
Like the Chebyshev inequality, care must be taken to assure both sequences are similarly ordered. Common strategies include:
- \(a \geq b \geq c \implies a+b \geq a+c \geq b+c\)
- \(a \geq b \geq c \implies \frac{1}{a} \leq \frac{1}{b} \leq \frac{1}{c}\)
Cycling the variables is also a powerful technique, as this preserves some ordering. For instance,
Show that
\[a^2+b^2+c^2 \geq ab+bc+ca\] for reals \(a,b,c\).
Solution:
Assume without loss of generality that \(a \geq b \geq c\). By rearrangement,
\[a \cdot a+b \cdot b+c \cdot c \geq a \cdot b+b \cdot c+c \cdot a\]
which is precisely the desired inequality.
A similar strategy leads to another proof of the AM-GM inequality:
Show that
\[a^4+b^4+c^4+d^4 \geq 4abcd\]
for positive reals \(a,b,c,d\).
Assume without loss of generality that \(a \leq b \leq c \leq d\). The rearrangement inequality tells us that:
\[d \cdot d^3+c \cdot c^3 \geq d \cdot c^3+c \cdot d^3 \implies d^4+c^4 \geq dc^3+cd^3\] \[d \cdot cd^2+b \cdot b^3 \geq d \cdot b^3+b \cdot cd^2 \implies cd^3+b^4 \geq db^3+bcd^2\] which implies that \[d^4+c^4+b^4 \geq dc^3+db^3+bcd^2\] Additionally, the rearrangement inequality tells us that \[d \cdot a^3+a \cdot bcd \geq d \cdot bcd+a \cdot a^3 \implies da^3+abcd \geq bcd^2+a^4\] which implies that \[d^4+c^4+b^4+a^4 \geq dc^3+db^3+da^3+abcd\] and so it suffices to show that \(dc^3+db^3+da^3 \geq 3abcd\), or \(a^3+b^3+c^3 \geq 3abc\). This argument is then repeated until it is left to prove that \(a \geq a\), which is self-evident.