Karamataの不等式(Karamata's inequality)とは、区間 $I$ の数の組 $x=(x_1,\dots,x_n)$ が $y=(y_1,\dots,y_n)$ を優越する(大きい順に並べた先頭 $k$ 個の和が $x$ のほうが大きいか等しく、全体の和は等しい)ならば、$I$ 上の任意の凸関数 $\varphi$ について $\sum\varphi(y_i)\le\sum\varphi(x_i)$ が成り立ち、逆にすべての凸関数で成り立てば $x$ は $y$ を優越する、という定理である。等しい重みの Jensen の不等式を特別な場合として含み、優越は二重確率行列による変換で特徴づけられる。
前提知識: 凸関数, Jensenの不等式
Karamataの不等式(Karamata's inequality)とは、区間 $I$ の数の組 $x=(x_1,\dots,x_n)$、$y=(y_1,\dots,y_n)$ について、$x$ が $y$ を 優越する(大きい順に並べた先頭 $k$ 個の和が $x$ のほうが大きいか等しく、全体の和は等しい)ならば、$I$ 上の任意の 凸関数 $\varphi$ について
$$
\varphi(y_1)+\cdots+\varphi(y_n)\le\varphi(x_1)+\cdots+\varphi(x_n)
$$
が成り立つ、という定理である。逆に、すべての凸関数でこの不等式が成り立てば $x$ は $y$ を優越する。
Jensenの不等式 は、$n$ 個の数の値の和 $\sum\varphi(x_i)$ を、すべてを平均 $m$ に置き換えた $n\varphi(m)$ と比べる。Karamata の不等式は、その比較を「より平均に寄った組」一般に広げる。数の組を平均の方へならすほど凸関数の値の和は減り、その「ならし」の順序が優越である。凸関数の和の大小を、組の比較という組合せ的な条件に完全に置き換えられる点に意味がある。三角形の角の三角関数の和、エネルギーやエントロピーの比較、固有値の不等式など、和の形の不等式の多くがこの定理から出る。
この記事では、優越を定義し、弦の傾きと部分和(Abel の総和法)による証明と、角を 1 つもつ凸関数を代入する証明で両方向を示す。さらに、二重確率行列による優越の特徴づけ、等号の条件、片側だけの優越(弱い優越)と増加凸関数の場合を述べる。
$x=(x_1,\dots,x_n)\in\mathbb{R}^n$ の成分を大きい順に並べ替えたものを $x^\downarrow=(x^\downarrow_1\ge\cdots\ge x^\downarrow_n)$ と書く。
$x,y\in\mathbb{R}^n$ について
$$
\sum_{i=1}^{k}y^\downarrow_i\le\sum_{i=1}^{k}x^\downarrow_i\quad(k=1,\dots,n-1),\qquad\sum_{i=1}^{n}y_i=\sum_{i=1}^{n}x_i
$$
が成り立つとき、$x$ は $y$ を 優越する(majorize)といい、$y\prec x$ と書く。
全体の和が等しいので、条件は「小さい順に並べた先頭 $k$ 個の和が $y$ のほうが大きいか等しい」と言い換えてもよい。$x$ のほうが大きい値と小さい値に偏っている、という意味である。たとえば和を $1$ にそろえると
$$
\Bigl(\tfrac13,\tfrac13,\tfrac13\Bigr)\prec\Bigl(\tfrac12,\tfrac12,0\Bigr)\prec(1,0,0)
$$
であり、成分の平均 $m$ だけからなる組 $(m,\dots,m)$ は、和が同じどの組にも優越される(ex-kar-jensen)。和が等しくても比べられない組もある(ex-kar-incomparable)。
$I\subset\mathbb{R}$ を区間とし、$x,y\in I^n$ とする。次の 2 つは同値である。
1 ならば 2 は、凸関数の弦の傾きの単調性(lem-kar-slopes)と部分和の公式で示す。2 ならば 1 は、1 次関数と角を 1 つもつ凸関数 $\max\{t-s,0\}$ を代入して示す。証明は prf-thm-kar-main にある。
$u\ne v$ について $S(u,v):=\frac{\varphi(u)-\varphi(v)}{u-v}$ とおく。$S(u,v)=S(v,u)$ である。
$\varphi$ を $I$ 上の凸関数とする。$u,v,u',v'\in I$、$u\ne v$、$u'\ne v'$、$u\ge u'$、$v\ge v'$ ならば $S(u,v)\ge S(u',v')$ である。
凸関数 の命題「凸関数の傾きの単調性」により、$p< q< r$ なら $S(p,q)\le S(p,r)\le S(q,r)$ である。これから、片方の端点を固定したとき $S$ はもう一方の端点について単調非減少である(3 点の大小の 3 通りを確かめればよい)。$u'\ne v$ なら $S(u,v)\ge S(u',v)\ge S(u',v')$ である。$u'=v$ でも $u\ne v'$ なら $S(u,v)\ge S(u,v')\ge S(u',v')$ である。$u'=v$ かつ $u=v'$ なら、$u\ge u'=v\ge v'=u$ より $u=v$ となり仮定に反する。$\square$
1 ならば 2。 両辺は成分の並べ替えで変わらないので、$x,y$ は大きい順に並んでいるとしてよい。$A:=\{i\mid x_i\ne y_i\}$ とし、$A$ が空なら示すことはない。$i\in A$ について $c_i:=S(x_i,y_i)$ とおく。$i< j$ がともに $A$ に属すれば、$x_i\ge x_j$、$y_i\ge y_j$ なので lem-kar-slopes により $c_i\ge c_j$ である。$i\notin A$ については、$i$ より大きい $A$ の最小の番号 $i'$ があれば $c_i:=c_{i'}$、なければ $i$ より小さい $A$ の最大の番号 $i'$ について $c_i:=c_{i'}$ とおく。こうすると $c_1\ge c_2\ge\cdots\ge c_n$ であり、すべての $i$ で $\varphi(x_i)-\varphi(y_i)=c_i(x_i-y_i)$ である($i\notin A$ では両辺が $0$)。
$D_k:=\sum_{i=1}^k(x_i-y_i)$ とおくと、1 から $D_k\ge0$($k< n$)、$D_n=0$ である。部分和の公式(Abel の総和法)により
$$
\sum_{i=1}^n\bigl(\varphi(x_i)-\varphi(y_i)\bigr)=\sum_{i=1}^nc_i(D_i-D_{i-1})=\sum_{k=1}^{n-1}(c_k-c_{k+1})D_k+c_nD_n\ge0
$$
である($D_0:=0$)。各項は $0$ 以上の数の積である。
2 ならば 1。 $\varphi(t)=t$ と $\varphi(t)=-t$ はどちらも凸なので、2 から $\sum y_i=\sum x_i$ である。$1\le k\le n-1$ とし、$x$ は大きい順に並んでいるとする。$s:=x_k$ とおき、凸関数 $\varphi_s(t):=\max\{t-s,0\}$ を使う。$x_i\ge s$($i\le k$)、$x_i\le s$($i>k$)なので $\sum_{i=1}^n\varphi_s(x_i)=\sum_{i=1}^k(x_i-s)$ である。一方、$y^\downarrow_1,\dots,y^\downarrow_k$ について $y^\downarrow_i-s\le\varphi_s(y^\downarrow_i)$ なので
$$
\sum_{i=1}^ky^\downarrow_i\le ks+\sum_{i=1}^k\varphi_s(y^\downarrow_i)\le ks+\sum_{i=1}^n\varphi_s(y_i)\le ks+\sum_{i=1}^n\varphi_s(x_i)=\sum_{i=1}^kx_i
$$
である(3 つ目の不等号が 2)。よって $y\prec x$ である。$\square$
1 ならば 2 の証明の要点は、凸関数を各点の組 $(x_i,y_i)$ の上で弦の傾き $c_i$ で「線形化」すると、傾きが番号について減っていることである。減っていく重み $c_i$ を掛けた和は、部分和 $D_k$ がすべて $0$ 以上なら $0$ 以上になる。2 ならば 1 の証明で使った $\max\{t-s,0\}$ は「角」を 1 つだけもつ凸関数である。Karamata の原論文は、凸関数を 1 次関数とこの形の関数の正の係数の和で近似する考え方で、この 2 種類の関数だけで条件を調べている(rem-kar-sources)。
成分がすべて $0$ 以上で、各行の和と各列の和がすべて $1$ の $n$ 次正方行列を **二重確率行列**(doubly stochastic matrix)という。置換行列は二重確率行列であり、二重確率行列の積も二重確率行列である。
$x,y\in\mathbb{R}^n$(縦ベクトル)について、$y\prec x$ であることと、ある二重確率行列 $P$ で $y=Px$ となることは同値である。
優越から行列を作る向きは、組を T 変換(下で定義する 1 回のならし)の有限列でつなぐ(lem-kar-transfer)。逆向きは Jensen の不等式で thm-kar-main の 2 に帰着させる。証明は prf-thm-kar-doubly-stochastic にある。
1 回の「ならし」は二重確率行列で書ける。$j\ne k$ と $\lambda\in[0,1]$ について、第 $j$・第 $k$ 成分だけを $x_j'=\lambda x_j+(1-\lambda)x_k$、$x_k'=(1-\lambda)x_j+\lambda x_k$ に替える操作を T 変換 という。行列で書くと $\lambda E+(1-\lambda)Q$($E$ は単位行列、$Q$ は $j$ と $k$ を入れ替える置換行列)であり、二重確率行列である。
$x,y$ が大きい順に並んでいて $y\prec x$、$y\ne x$ ならば、$x$ に $\lambda\in(0,1)$ の T 変換を 1 回施した組 $x'$ で、$x'$ も大きい順に並び、$y\prec x'$ であり、$x'_i=y_i$ となる番号 $i$ の個数が増えるものがある。とくに、高々 $n-1$ 回の T 変換で $x$ から $y$ に着く。
$j$ を $x_j>y_j$ となる最大の番号、$k$ を $k>j$ かつ $x_k< y_k$ となる最小の番号とし、$\delta:=\min\{x_j-y_j,\ y_k-x_k\}$、$\lambda:=\frac{x_j-\delta-x_k}{x_j-x_k}$ とおくと、第 $j$ 成分を $x_j-\delta$、第 $k$ 成分を $x_k+\delta$ に替えた組が求める $x'$ である。$x_j-\delta\ge y_j\ge y_k\ge x_k+\delta>x_k$ なので $0< \lambda< 1$ である。
$x\ne y$ で全体の和が等しいので、$x_i\ne y_i$ となる最大の番号 $m$ では、先頭 $m-1$ 個の和の比較と先頭 $m$ 個の和の一致から $x_m< y_m$ である。また $x_i>y_i$ となる $i$ がある(最初に $x_i\ne y_i$ となる番号では、それまでの和が等しく先頭からの和は $x$ が大きいか等しいので $x_i>y_i$)。$j$ はそのうち最大のもので、$j< m$ なので $k$ が存在する。$j< i< k$ では $x_i=y_i$ である。$x'_{j}=x_j-\delta\ge y_j\ge y_{j+1}$ と $x'_k=x_k+\delta\le y_k\le y_{k-1}$ から($j+1=k$ なら上の不等式から)$x'$ は大きい順に並ぶ。先頭からの和は $j\le r< k$ でだけ $\delta$ 減り、そこでは $\sum_{i\le r}x'_i=\sum_{i< j}x_i+(x_j-\delta)+\sum_{j< i\le r}y_i\ge\sum_{i\le r}y_i$ である。$\delta$ の選び方から $x'_j=y_j$ か $x'_k=y_k$ の少なくとも一方が成り立つ。同じ議論は Muirheadの不等式 の補題「ならしの列の存在」にもある。$\square$
優越ならば。 置換行列 $R$、$R'$ で $Rx=x^\downarrow$、$R'y=y^\downarrow$ とする。lem-kar-transfer から T 変換の行列 $T_1,\dots,T_m$ で $y^\downarrow=T_m\cdots T_1x^\downarrow$ となるものがあり、$P:=R'^{-1}T_m\cdots T_1R$ は二重確率行列で $y=Px$ である。
二重確率行列ならば。 $y=Px$、$P=(p_{ij})$ とし、$I$ を $x$ の成分を含む区間、$\varphi$ を $I$ 上の凸関数とする。各行の和が $1$ なので $y_i=\sum_jp_{ij}x_j$ は $x$ の成分の凸結合で $I$ に属し、凸関数 の定理「有限個の点のJensenの不等式」から $\varphi(y_i)\le\sum_jp_{ij}\varphi(x_j)$ である。$i$ について足すと、各列の和が $1$ なので $\sum_i\varphi(y_i)\le\sum_j\varphi(x_j)$ である。thm-kar-main の 2 ならば 1 から $y\prec x$ である。$\square$
$\varphi$ が $I$ 上で狭義凸、$x,y\in I^n$、$y\prec x$ で、$y^\downarrow\ne x^\downarrow$ ならば、$\sum\varphi(y_i)< \sum\varphi(x_i)$ である。
$x,y$ は大きい順に並んでいるとしてよい。lem-kar-transfer の最初の T 変換 $x\to x'$ は、2 つの値 $a:=x_j>b:=x_k$ を $\lambda a+(1-\lambda)b$ と $(1-\lambda)a+\lambda b$($0< \lambda< 1$)に替える。狭義凸性から
$$
\varphi(\lambda a+(1-\lambda)b)+\varphi((1-\lambda)a+\lambda b)< \lambda\varphi(a)+(1-\lambda)\varphi(b)+(1-\lambda)\varphi(a)+\lambda\varphi(b)=\varphi(a)+\varphi(b)
$$
なので $\sum\varphi(x'_i)< \sum\varphi(x_i)$ である。$y\prec x'$ なので thm-kar-main から $\sum\varphi(y_i)\le\sum\varphi(x'_i)$ である。$\square$
全体の和の等号を外した条件 $\sum_{i\le k}y^\downarrow_i\le\sum_{i\le k}x^\downarrow_i$($k=1,\dots,n$)を 弱い優越(下からの優越)といい、$y\prec_wx$ と書く。
$x,y\in I^n$ について、$y\prec_wx$ であることと、$I$ 上の任意の単調非減少な凸関数 $\varphi$ について $\sum\varphi(y_i)\le\sum\varphi(x_i)$ であることは同値である。
弱い優越ならば:prf-thm-kar-main の 1 ならば 2 と同じ式で、$D_n\ge0$ になるだけが違う。$\varphi$ が単調非減少なら弦の傾きはすべて $0$ 以上なので $c_n\ge0$ であり、$c_nD_n\ge0$ である。逆:$\varphi_s(t)=\max\{t-s,0\}$ は単調非減少な凸関数なので、prf-thm-kar-main の 2 ならば 1 の計算が $k=1,\dots,n$ のすべてでそのまま通る($k=n$ では $s:=x^\downarrow_n$)。$\square$
$x\in I^n$ の平均を $m$ とし、$y:=(m,\dots,m)$ とする。大きい順に並べた $x$ の先頭 $k$ 個の平均は全体の平均 $m$ 以上なので $\sum_{i\le k}x^\downarrow_i\ge km$ であり、$y\prec x$ である。thm-kar-main から $n\varphi(m)\le\sum\varphi(x_i)$、すなわち等しい重みの Jensenの不等式 $\varphi\bigl(\frac1n\sum x_i\bigr)\le\frac1n\sum\varphi(x_i)$ を得る。Karamata は原論文の最後でこの系を注意している(Kar32 p. 148)。
三角形の角 $A\ge B\ge C>0$ が $A\le\frac\pi2$ を満たす(鈍角でない)とする。$x:=(\frac\pi2,\frac\pi2,0)$ とすると、$A\le\frac\pi2$、$A+B=\pi-C\le\pi$、$A+B+C=\pi$ なので $(A,B,C)\prec x$ である。$\varphi(t)=-\sin t$ は $[0,\frac\pi2]$ で $\varphi''=\sin t\ge0$、$(0,\frac\pi2]$ で正なので狭義凸である。$C>0$ なので $(A,B,C)\ne x$ であり、prop-kar-strict から
$$
\sin A+\sin B+\sin C>\sin\frac\pi2+\sin\frac\pi2+\sin0=2
$$
である。上からは ex-kar-jensen により $\sin A+\sin B+\sin C\le3\sin\frac\pi3=\frac{3\sqrt3}2$ である。鈍角でないという条件は外せない。角が $150^\circ,15^\circ,15^\circ$ なら和は $\frac12+2\sin15^\circ\approx1.018$ で、$2$ より小さい。このとき $A>\frac\pi2$ で $(A,B,C)\prec x$ が成り立たない。
$x=(5,1,0)$、$y=(4,3,-1)$ は和がともに $6$ で、先頭 1 個の和は $5>4$、先頭 2 個の和は $6< 7$ なので、どちらも他方を優越しない。thm-kar-main から、凸関数によって不等式の向きが変わるはずである。実際、$\varphi(t)=\max\{t-4,0\}$ では $\sum\varphi(x_i)=1>0=\sum\varphi(y_i)$、$\varphi(t)=\max\{t-1,0\}$ では $\sum\varphi(x_i)=4< 5=\sum\varphi(y_i)$ である。2 つ目は prf-thm-kar-main の $k=2$、$s=x_2=1$ の関数である。
$x=(3,1,0)$、$y=(2,1,1)$ では、先頭からの和が $3,4,4$ と $2,3,4$ なので $y\prec x$ である。lem-kar-transfer の手順では $j=1$、$k=3$、$\delta=1$、$\lambda=\frac{3-1-0}{3-0}=\frac23$ で、1 回の T 変換
$$
y=\begin{pmatrix}\frac23&0&\frac13\\0&1&0\\\frac13&0&\frac23\end{pmatrix}x
$$
で $y$ に着く。$\varphi(t)=t^2$ なら $\sum y_i^2=6< 10=\sum x_i^2$ で、prop-kar-strict のとおり等号は成り立たない。
和を固定した組の上で、thm-kar-main から $\sum x_i^2$(したがって分散)と $\sum x_i\log x_i$(成分が正のとき)は「優越について増える」関数であり、確率分布 $p$ のエントロピー $-\sum p_i\log p_i$ は「優越について減る」関数である。すべての $p$ は一様分布 $(\frac1n,\dots,\frac1n)$ を優越するので、エントロピーは一様分布で最大になる。優越について増える関数を Schur 凸関数 という。
| 外す仮定 | 反例 | 成り立たなくなること |
|---|---|---|
| $\varphi$ の凸性 | $\varphi(t)=-t^2$、$x=(1,0)$、$y=(\frac12,\frac12)$ | $\sum\varphi(y_i)=-\frac12>-1=\sum\varphi(x_i)$ |
| 全体の和の等号 | $x=(1,1)$、$y=(0,0)$、$\varphi(t)=-t$ | 先頭からの和は $x$ が大きいが、$\sum\varphi(y_i)=0>-2=\sum\varphi(x_i)$ |
| prop-kar-weak の単調性 | $I=[-1,0]$、$x=(0,0)$、$y=(-1,-1)$、$\varphi(t)=t^2$ | $y\prec_wx$ だが $\sum\varphi(y_i)=2>0=\sum\varphi(x_i)$ |
| prop-kar-strict の狭義凸性 | $\varphi(t)=\max\{t,0\}$、$x=(2,1)$、$y=(\frac32,\frac32)$ | $y^\downarrow\ne x^\downarrow$ だが両辺とも $3$ で等号 |
1 行目:$(\frac12,\frac12)\prec(1,0)$ であり、$-t^2$ は凹関数である。凹関数では不等式が逆向きになる。2 行目:先頭 1 個・2 個の和は $1\ge0$、$2\ge0$ だが、全体の和が $2\ne0$ で優越の定義を満たさない。$-t$ は 1 次関数で凸である。3 行目:先頭からの和は $-1\le0$、$-2\le0$ で弱い優越が成り立つ。$t^2$ は $[-1,0]$ で凸だが単調減少である。4 行目:$\max\{t,0\}$ は凸だが狭義凸でなく、$x,y$ の成分がすべて $0$ 以上の所では 1 次関数 $t$ に一致する。$\square$
J. Karamata は 1932 年の論文で、区間の $2n$ 個の数について、すべての凸関数で $\sum f(x_\nu)\le\sum f(X_\nu)$ が成り立つための条件を問い、個数の関数の Stieltjes 積分に書き直して、1 次関数と $|t-u|$ の形の関数で条件を調べ、thm-kar-main と同値な定理を述べている(Kar32 pp. 145–148。数を小さい順に並べ、小さい方からの部分和で条件を書く)。同論文の最後では Jensen の不等式がその特別な場合であることを注意している(p. 148)。この記事の prf-thm-kar-main の部分和による証明、thm-kar-doubly-stochastic・prop-kar-strict・prop-kar-weak の証明は書き下ろしたものである。
Muirheadの不等式 は、正の数の単項式を並べ替えて平均した量の大小が、指数の組の優越で決まることを述べる。$x=(e^c,1,\dots,1)$ のように 1 つの変数だけを動かすと、その不等式は $\varphi(t)=e^{ct}$ についての thm-kar-main の不等式になる。同記事の命題「優越と凸関数」は thm-kar-main の 1 ならば 2 を T 変換で示している。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する