前提知識

Majorization

降順に並んだ$n$個の実数の組$x=(x_1,x_2,\ldots,x_n), y=(y_1,y_2,\ldots,y_n)\ (x_i\ge x_{i+1}, y_i\ge y_{i+1})$について, 以下が成り立つとき$x$は$y$をmajorizeすると言い, $x\succ y$と書く.

$$\begin{aligned}\displaystyle &\sum_{i=1}^{k} x_i \ge \sum_{i=1}^{k} y_i\ \ (k=1,2,\ldots, n-1),\\[14pt] &\displaystyle\sum_{i=1}^{n} x_i \ge \sum_{i=1}^{n} y_i. \end{aligned}$$

簡単に言うと全成分の和が同じ$x,y$同士でより成分の値が偏ってる方を"大きい"ものとしましょうという概念です. 例えば以下の通り.

$$(3,2,1)\succ(2,2,2), \quad (4,0,0)\succ(2,1,1), \quad (1,0,-1)\succ (0,0,0).$$

$x\succ y$の特徴付けとして以下が知られています.

補題

$x\succ y$になるためにはある二重確率行列$P$が存在して$y=Px$と書けることが必要十分である.

※全成分が0以上かつ全ての行和および列和が1である行列を二重確率行列と呼びます.

Karamataの不等式

$f:\R\to\R$を凸関数とする. $x=(x_1,x_2,\ldots,x_n), y=(y_1,y_2,\ldots,y_n)$について$x\succ y$のとき次の不等式が成り立つ.

$$f(x_1)+\cdots +f(x_n) \ge f(y_1)+\cdots +f(y_n)$$

証明

先の補題より$x\succ y$のときある二重確率行列$P$が存在して$y=Px$. ゆえに,

$$\begin{aligned} \sum_{j=1}^n f(x_j)&= \sum_{j=1}^n \left(\sum_{i=1}^n P_{ij}\right)f(x_j)\\ &= \sum_{i=1}^n \sum_{j=1}^n P_{ij} f(x_j)\\ &\ge \sum_{i=1}^n f\left(\sum_{j=1}^n P_{ij} x_j\right) \quad (\text{by Jensen's})\\ &= \sum_{i=1}^n f(y_i). \end{aligned}$$

応用例

$a\ge b \ge c$について,

$$\left(2a,2b,2c\right) \succ (a+b, b+c, c+a)$$

が成り立つので, Karamataの不等式より凸関数$f$に対して

$$f(2a)+ f(2b)+ f(2c) \ge f(a+b)+f(b+c)+f(c+a)$$

です. 得られた不等式は$a,b,c$に対して対称なのでこれは任意の$a,b,c$についても言えます.

同様に

$$\left(a^2+ab+b^2,b^2+bc+c^2,c^2+ca+a^2 \right) \succ (a^2+b^2+c^2, a^2+b^2+c^2, ab+bc+ca)$$

なので

$$f(a^2+ab+b^2)+f(b^2+bc+c^2)+f(c^2+ca+a^2) \ge 2f(a^2+b^2+c^2) + f(ab+bc+ca)$$

なども成り立ちます.

$f(x)=1/x$とか$f(x)=\sqrt x$(この場合はconcaveなので不等号の向きが逆になる)を入れるだけでも結構非自明な不等式になる.