1. 高校数学の美しい物語
  2. 対数和不等式の証明と応用

対数和不等式の証明と応用

更新日時 2021/03/07

対数和不等式(Log sum inequality)

a1,a2,,an,b1,b2,,bna_1,a_2,\cdots,a_n,b_1,b_2,\cdots,b_n を正の数とするとき,

aklogakbk(ak)logakbk\sum a_k\log\dfrac{a_k}{b_k}\geq(\sum a_k)\log\dfrac{\sum a_k}{\sum b_k}

主に情報理論で活躍する不等式です。この記事では k=1n\displaystyle\sum_{k=1}^n のことを \sum と書きます。

目次
  • 対数和不等式の証明

  • KLダイバージェンスの非負性

  • エントロピー最大の分布

対数和不等式の証明

f(x)=xlogxf(x)=x\log xイェンゼンの不等式を用いるだけです!

f(x)=xlogxf(x)=x\log x は入試でも頻出の重要な関数です。凸であることは覚えておきましょう。→xlogxの極限,グラフ,積分など

証明

f(x)=xlogxf(x)=x\log x とおくと,f(x)f(x) の微分は logx+1\log x+1 ,二階微分は 1x\dfrac{1}{x} なので f(x)f(x)x>0x> 0 で凸関数である。

ここで,bkbk=λk\dfrac{b_k}{\sum b_k}=\lambda_k とおくと対数和不等式の左辺は

aklogakbk=bkakbklogakbk=(bk)λkf(akbk)\sum a_k\log\dfrac{a_k}{b_k}\\ =\sum b_k\dfrac{a_k}{b_k}\log\dfrac{a_k}{b_k}\\ =(\sum b_k)\sum \lambda_k f\left(\dfrac{a_k}{b_k}\right)

となる。これにイェンゼンの不等式を用いると,

(上式)

(bk)f(λkakbk)=(bk)f(akbk)=(ak)logakbk\geq (\sum b_k)f\left(\sum\lambda_k\dfrac{a_k}{b_k}\right)\\ =(\sum b_k)f\left(\dfrac{\sum a_k}{\sum b_k}\right)\\ =(\sum a_k)\log \dfrac{\sum a_k}{\sum b_k}

となり目標の式を得る。

等号成立条件は(イェンゼンの不等式の等号成立条件より)b1a1=b2a2==bnan\dfrac{b_1}{a_1}=\dfrac{b_2}{a_2}=\cdots=\dfrac{b_n}{a_n} です。

ちなみに,ak,bka_k,b_k の中に 00 がある場合にも(0log0bk=00\log\dfrac{0}{b_k}=0aklogak0=(ak0)a_k\log\dfrac{a_k}{0}=\infty\:(a_k\neq 0) とみなすことで)対数和不等式は拡張できます。

KLダイバージェンスの非負性

対数和不等式の応用例です。

ギブスの不等式:

pk=qk=1\sum p_k=\sum q_k=1pk,qkp_k,q_k が非負のとき,

D(PQ)=pklogpkqk0D(P\| Q)=\sum p_k\log\dfrac{p_k}{q_k}\geq 0

D(PQ)D(P\| Q) はカルバック–ライブラー情報量,Kullback–Leibler divergenceなどと呼ばれる重要な量です。二つの確率分布 P,QP,Q の間の距離のようなもの(厳密には距離ではありません)です。

証明

対数和不等式で ak=pk,bk=qka_k=p_k,b_k=q_k とすればよい。 pk=qk=1\sum p_k=\sum q_k=1 を使うと右辺は 00 になる。

ちなみに D(PQ)0D(P\|Q)\geq 0 の等号成立条件は全ての kk について pk=qkp_k=q_k であること,つまり二つの確率分布が等しいことです。

ギブスの不等式は入試でもまれに登場します。→有名不等式logx≦x-1の証明と入試問題

エントロピー最大の分布

pk=1\sum p_k=1pkp_k が非負のとき,

H(P)=pklogpklognH(P)=-\sum p_k\log p_k\leq \log n

等号成立条件は p1=p2==pnp_1=p_2=\cdots=p_n ,つまり PP が一様分布のときです。

H(P)H(P) はエントロピーと呼ばれる重要な量です。

証明

ギブスの不等式を変形すると,

pklogpkpklogqk-\sum p_k\log p_k\leq -\sum p_k\log q_k

ここで,qk=1n(k=1,2,,n)q_k=\dfrac{1}{n}\:(k=1,2,\cdots,n) とすると右辺は logn\log n となる。

今日のネタは情報理論に強い知人のN氏によるものです,感謝!

人気記事
  1. 高校数学の美しい物語
  2. 対数和不等式の証明と応用