Karamata's inequality
In mathematics, Karamata's inequality,[1] named after Jovan Karamata,[2] also known as the majorization inequality, is a theorem in elementary algebra for convex and concave real-valued functions, defined on an interval of the real line. It generalizes the discrete form of Jensen's inequality.
Contents
Statement of the inequality
Let I be an interval of the real line and let f denote a real-valued, convex function defined on I. If x1, . . . , xn and y1, . . . , yn are numbers in I such that (x1, . . . , xn) majorizes (y1, . . . , yn), then
-
(1)
Here majorization means that
-
(2)
and, after relabeling the numbers x1, . . . , xn and y1, . . . , yn, respectively, in decreasing order, i.e.,
-
and
(3)
we have
-
for all i ∈ {1, . . . , n − 1}.
(4)
If f is a strictly convex function, then the inequality (1) holds with equality if and only if, after relabeling according to (3), we have xi = yi for all i ∈ {1, . . . , n}.
Remarks
- If the convex function f is non-decreasing, then the proof of (1) below and the discussion of equality in case of strict convexity shows that the equality (2) can be relaxed to
-
-
(5)
-
Example
The finite form of Jensen's inequality is a special case of this result. Consider the real numbers x1, . . . , xn ∈ I and let
denote their arithmetic mean. Then (x1, . . . , xn) majorizes the n-tuple (a, a, . . . , a), since the arithmetic mean of the i largest numbers of (x1, . . . , xn) is at least as large as the arithmetic mean a of all the n numbers, for every i ∈ {1, . . . , n − 1}. By Karamata's inequality (1) for the convex function f,
Dividing by n gives Jensen's inequality. The sign is reversed if f is concave.
Proof of the inequality
We may assume that the numbers are in decreasing order as specified in (3).
If xi = yi for all i ∈ {1, . . . , n}, then the inequality (1) holds with equality, hence we may assume in the following that xi ≠ yi for at least one i.
If xi = yi for an i ∈ {1, . . . , n − 1}, then the inequality (1) and the majorization properties (2), (4) are not affected if we remove xi and yi. Hence we may assume that xi ≠ yi for all i ∈ {1, . . . , n − 1}.
It is a property of convex functions that for two numbers x ≠ y in the interval I the slope
of the secant line through the points (x, f (x)) and (y, f (y)) of the graph of f is a monotonically non-decreasing function in x for y fixed (and vice versa). This implies that
-
(6)
for all i ∈ {1, . . . , n − 1}. Define A0 = B0 = 0 and
for all i ∈ {1, . . . , n}. By the majorization property (4), Ai ≥ Bi for all i ∈ {1, . . . , n − 1} and by (2), An = Bn. Hence,
-
Failed to parse (Missing <code>texvc</code> executable. Please see math/README to configure.): \begin{align} \sum_{i=1}^n \bigl(f(x_i) - f(y_i)\bigr) &=\sum_{i=1}^n c_i (x_i - y_i)\\ &=\sum_{i=1}^n c_i \bigl(\underbrace{A_i - A_{i-1}}_{=\,x_i}{} - (\underbrace{B_i - B_{i-1}}_{=\,y_i})\bigr)\\ &=\sum_{i=1}^n c_i (A_i - B_i) - \sum_{i=1}^n c_i (A_{i-1} - B_{i-1})\\ &=c_n (\underbrace{A_n-B_n}_{=\,0}) + \sum_{i=1}^{n-1}(\underbrace{c_i - c_{i + 1}}_{\ge\,0})(\underbrace{A_i - B_i}_{\ge\,0}) - c_1(\underbrace{A_0-B_0}_{=\,0})\\ &\ge0, \end{align}
(7)
which proves Karamata's inequality (1).
To discuss the case of equality in (1), note that x1 > y1 by (4) and our assumption xi ≠ yi for all i ∈ {1, . . . , n − 1}. Let i be the smallest index such that (xi, yi) ≠ (xi+1, yi+1), which exists due to (2). Then Ai > Bi. If f is strictly convex, then there is strict inequality in (6), meaning that ci+1 < ci. Hence there is a strictly positive term in the sum on the right hand side of (7) and equality in (1) cannot hold.
If the convex function f is non-decreasing, then cn ≥ 0. The relaxed condition (5) means that An ≥ Bn, which is enough to conclude that cn(An−Bn) ≥ 0 in the last step of (7).
If the function f is strictly convex and non-decreasing, then cn > 0. It only remains to discuss the case An > Bn. However, then there is a strictly positive term on the right hand side of (7) and equality in (1) cannot hold.
References
External links
An explanation of Karamata's inequality and majorization theory can be found here.