Suppose that $f$ is a convex function and $\{x_i\}_{i=1}^n$ and $\{y_i\}_{i=1}^n$ are real numbers such that $x_1\leq x_2\leq \dots \leq x_n$ and $y_1\leq y_2\leq \dots \leq y_n$. Let $\{u_i\}_{i=1}^n$ be any permutation of $y_i$'s. Then $$f(x_1+y_n)+f(x_2+y_{n-1})+\dots+f(x_n+y_1)\leq f(x_1+u_1)+f(x_2+u_{2})+\dots+f(x_n+u_n)\leq $$ $$\leq f(x_1+y_1)+f(x_2+y_2)+\dots+f(x_n+y_n).$$
In my book it is called as Generalized rearrangement inequality. I do know the regular rearrangement inequality and its proof.
I have no ideas how to prove the above inequality and how the regular one follows from it?
Would be very grateful for help!
Best Answer
One can proceed similarly as in the proof of the “regular” rearrangement inequality: If $\sigma$ is a permutation of $\{1, \ldots ,n\}$ and not the identity then there are indices $j < k$ such that exchanging $\sigma(j)$ and $\sigma(k)$ gives a new permutation $\tau$ with more fixed points than $\sigma$ and $$ \tag{*} \sum_{i=1}^n f(x_i + y_{\sigma(i)}) \le \sum_{i=1}^n f(x_i + y_{\tau(i)}) \, . $$ If $\tau$ is not the identity then this step can be repeated, and after finitely many steps one obtains $$ \sum_{i=1}^n f(x_i + y_{\sigma(i)}) \le \sum_{i=1}^n f(x_i + y_i) \, . $$
In the case of the “regular” rearrangement inequality one uses that for $a_1 \le a_2$ and $b_1 \le b_2$ $$ (a_2-a_1)(b_2-b_1) \ge 0 \implies a_1 b_2 + a_2 b_1 \le a_1 b_1 + a_2 b_2 \, . $$ In our case one can use the following to prove $(*)$:
This holds trivially if $a_1 =a_2$ or $b_1 = b_2$. In the case $a_1 < a_2$ and $b_1 < b_2$ it follows from adding the convexity conditions: $$ f(a_1 + b_2) \le \frac{a_2-a_1}{a_2+b_2-a_1-b_1} f(a_1 + b_1) + \frac{b_2 - b_1}{a_2+b_2-a_1-b_1} f(a_2 + b_2) \\ f(a_2 + b_1) \le \frac{b_2-b_1}{a_2+b_2-a_1-b_1} f(a_1 + b_1) + \frac{a_2 - a_1}{a_2+b_2-a_1-b_1} f(a_2 + b_2) $$
For positive sequences $u_1, \ldots, u_n$ and $v_1, \ldots, v_n$ the normal rearrangement inequality follows from the generalized one with $f(t)=e^t$ applied to $x_i = \log u_i$ and $y_i = \log v_i$, since then $$ f(x_i + y_{\sigma(i)}) = u_i \cdot v_{\sigma(i)} \ . $$
It is also a consequence of Karamata's inequality: Set $$ (a_1, a_2, \ldots , a_n) = (x_n + y_n, x_{n-1}+y_{n-1}, \ldots, x_1 + y_1) $$ and let $(b_1, b_2, \ldots , b_n)$ be a decreasing rearrangement of $$ (x_n + u_n, x_{n-1}+u_{n-1}, \ldots, x_1 + u_1) \, . $$ Then $$ (a_1,a_2,\ldots,a_n)\succ(b_1,b_2,\ldots,b_n) $$ so that $$ f(a_1)+f(a_2)+ \ldots +f(a_n) \ge f(b_1)+f(b_1)+ \ldots +f(b_n) $$ which is the desired conclusion.