[別館]球面倶楽部零八式markIISR

東大入試数学中心。解説なので解答としては不十分。出題年度で並ぶようにしている。大人の解法やうまい解法は極めて主観的に決めている。

2023年(令和5年)京都大学理学部特色入試・数理科学入試-数学[2]

2023.01.22記

[2] 2つの整数 m と n が 0\lt m\lt n を満たすとする．また，関数 H(x) を
H(x)=-x\log x-(1-x)\log x（0\lt x\lt 1）
と定める．ただし，\log は自然対数を表す．また，e を自然対数の底とする．以下の設問に答えよ．

(1) {}_n\mbox{C}_m\leqq e^{nH\left(\frac{m}{n}\right)} が成り立つことを示せ．

(2) 0\leqq k\leqq n を満たす任意の整数 k に対して
{}_n\mbox{C}_k\left(\dfrac{m}{n}\right)^{k}\left(1-\dfrac{m}{n}\right)^{n-k}\leqq {}_n\mbox{C}_m\left(\dfrac{m}{n}\right)^{m}\left(1-\dfrac{m}{n}\right)^{n-m}
が成り立つことを示せ．

(3) {}_n\mbox{C}_m\geqq \dfrac{1}{n+1}e^{nH\left(\frac{m}{n}\right)} が成り立つことを示せ．

本問のテーマ
シャノンエントロピー
タイプ理論

2023.01.22記
二項定理の x^m (1-x)^{n-m} の対数が
m\log x+(n-m)\log(1-x)=-nH(x)
（x=\dfrac{m}{n}）となることに気付けば，

[2] 2つの整数 m と n が 0\lt m\lt n を満たすとし，x=\dfrac{m}{n}）とおくとする．

(1) {}_n\mbox{C}_m x^{m}(1-x)^{n-m}\leqq 1
が成り立つことを示せ．

(2) 0\leqq k\leqq n を満たす任意の整数 k に対して，
{}_n\mbox{C}_k x^{k} (1-x)^{n-k}\leqq {}_n\mbox{C}_m x^{m} (1-x)^{n-m}
が成り立つことを示せ．

(3) 1\leqq (n+1) {}_n\mbox{C}_m x^{m}(1-x)^{n-m} が成り立つことを示せ．

となり，結構簡単な二項定理の応用問題であることに気付く．

(1) は 0\lt x\lt 1 のときに {}_n\mbox{C}_m x^{m}(1-x)^{n-m}\leqq 1 となることは，二項係数の総和が1となる二項定理からほぼ自明である．

(2) は単峰である二項分布の最頻値を求める問題で，一般の {}_n\mbox{C}_k x^{k}(1-x)^{n-k} を最大にする k は
r\leqq (n+1)x
をみたす最大の r である（その r が k=(n+1)xをみたすときは k=r-1，r となる）ことの応用で，本問では
r\leqq (n+1)\dfrac{m}{n}=m+\dfrac{m}{n}(\lt m+1)
であるから，k=m となり，題意は成立する．

(3) この不等式をみて，(2)で k=0,\ldots,n の場合の n+1 個の式を足しあげることに気付かないとちょっと．

[解答]
(1) x=\dfrac{m}{n} とおくと二項定理より
\displaystyle\sum_{k=0}^n {}_n\mbox{C}_k x^k(1-x)^{n-k}=1
である．ここで 0\leqq x\leqq 1 だから．和を構成する項はすべて非負であるから
全ての項は0以上1以下となり，特に
{}_n\mbox{C}_m x^m(1-x)^{n-m}\leqq 1
である．ここで
x^m(1-x)^{n-m}=e^{m\log x+(n-m)\log (1-x)}=e^{-nH(x)}
であるから
{}_n\mbox{C}_m e^{-nH(x)}\leqq 1
となり
{}_n\mbox{C}_m \leqq e^{nH(x)}=e^{nH(m/n)}
となる．

(2) f(k)={}_n\mbox{C}_k\left(\dfrac{m}{n}\right)^{k}\left(1-\dfrac{m}{n}\right)^{n-k}
とおくと k=1,2,\ldots,n に対して
\dfrac{f(k)}{f(k-1)}=\dfrac{(n-k+1)m}{k(n-m)}\geqq 1
なる k の条件は分母正より
(n-k+1)m\geqq k(n-m)
から
k\leqq \dfrac{(n+1)m}{n}=m+\dfrac{m}{n}(\lt m+1)
となるので
f(0)\lt f(1)\lt\cdots\lt f(m) \gt f(m+1) \gt \cdots \gt f(n)
が成立し，題意は示された．

(3) (2) の不等式を k=0,\ldots,n と合計すると
1=\displaystyle \sum_{k=0}^n {}_n\mbox{C}_k x^k(1-x)^{n-k}\leqq (n+1) {}_n\mbox{C}_m x^m(1-x)^{n-m}=(n+1) {}_n\mbox{C}_m e^{-nH(x)}
よって
{}_n\mbox{C}_m\geqq \dfrac{1}{n+1}e^{nH\left(\frac{m}{n}\right)}
である．


シャノンエントロピー

情報理論では確率 p_1,\ldots,p_n(値は非負で和は1)で起こる事象の（シャノン）エントロピーを
H(p_1,\ldots,p_n)=-\displaystyle\sum_{k=1}^n p_k\log p_k （0\log0=0と約束する）
で定める．ここで対数の底は2または自然対数の底 e とするのが一般的であるが一般には底を1より大きくとるものとする．

このとき，0\leqq p_k\leqq 1 により -p_k\log p_k\geqq 0 だから，エントロピーは非負の項の和となり，非負であることがわかる．

離散確率変数 X が {\cal X}=\{x_1,\ldots,x_n\}に値をとるとし，\textsf{P}(X=x_k)=p_k とするとき，確率変数 X のエントロピーは
H(X)=-\displaystyle\sum_{x\in{\cal X}} p(x)\log p(x)
と書くことができる．ここでエントロピーの値は実現値の値ではなく確率分布だけで決まり，しかも p_k の順番にもよらないことに注意しよう．つまり，X の分布ではなく p_k の分布によって定まる量であることに注意しておく．

同時エントロピー，条件付きエンロピー，相互情報量

同時エントロピー
H(X,Y)=-\displaystyle\sum_{x\in{\cal X}}\sum_{y\in{\cal Y}} p(x,y)\log p(x,y)
や条件付エントロピー
H(X|Y)=-\displaystyle\sum_{x\in{\cal X}}\sum_{y\in{\cal Y}} p(x,y)\log p(x|y)
も定義される．そして相互情報量を
I(X;Y)=\displaystyle\sum_{x\in{\cal X}}\sum_{y\in{\cal Y}} p(x,y)\log \dfrac{p(x,y)}{p(x)p(y)}
で定義すると，
I(X;Y)=H(X)-H(X|Y)，
I(Y;X)=I(X;Y)，
I(X;X)=H(X)
などが成立する．

KLダイバージェンスと情報不等式

相対エントロピーまたはカルバックライブラー(KL)ダイバージェンスは
D(p||q)=\displaystyle\sum_{x\in{\cal X}}p(x)\log\dfrac{p(x)}{q(x)}
によって定義される確率分布の(2乗)距離と対応付けられる量である．Jensen の不等式を用いると
D(p||q)=-\displaystyle\sum_{x\in{\cal X}}p(x)\log\dfrac{q(x)}{p(x)}
\geqq -\log\left(\displaystyle\sum_{x\in{\cal X}}p(x)\dfrac{q(x)}{p(x)}\right)=-\log 1=0
であるから非負である（等号は p(x)\equiv q(x) ）．これは情報不等式と呼ばれる．

情報不等式は例えば
1990年(平成2年)東京工業大学前期数学[2] - [別館]球面倶楽部零八式markIISR
のように大学入試でも扱われている．

相対エントロピーを用いて
I(X;Y)=D(p(x,y)||p(x)p(y))
と表すことができるので，相互情報量は非負であり，一般的には X と Yに共通に含まれる情報量と解釈される．定義からも明らかであるが，これと H(X)=I(X;X) からシャノンエントロピーも非負であることがわかる．

情報量とエントロピー

I(X;Y)=H(X)-H(X|Y)
という式は，Xのもつ情報量（エントロピー） H(X) と Y を知ったときにまだ X に残っている情報量 H(X|Y) の差は， X と Yに共通に含まれる情報量 I(X;Y) になるという式になっている．

X,Yが独立のとき，定義から I(X;Y)=0 である．独立であるから共通に含まれる情報量が0であると解釈される．このとき，H(X|Y)=H(X) となることもわかる．

一般にH(X,Y)はX,Yに含まれる情報量であるが，ベン図の要領で
H(X,Y)=H(X)+H(Y)-I(X;Y)
であることがわかり，X,Yが独立のときH(X,Y)=H(X)+H(Y)が成立する．

ベルヌイ試行のエントロピー

このとき，ベルヌイ試行（表がでる確率が x，裏がでる確率が 1-x のコインを1回投げる）のシャノンエントロピーは
H(x)=-x\log x-(1-x)\log x（0\lt x\lt 1）
となる．これはコイン投げ1回当りの情報量を表す．通常は対数の底を 2 とし，単位を bit で表すが，自然対数を底とした場合の単位は nat であり，1 nat は \log_e 2 bit である．

さて，表が出る確率が x であるベルヌイ試行を n 回行うことを考え，その確率変数を X_1,\ldots,X_n とする．
これは独立試行であるから
H(X_1,\ldots,X_n)=nH(X_1)=nH(x)（このH(x)は問題文の H(x)）
が成立する．

タイプ理論

T 文字のアルファベット a_1,\ldots,a_T があり，その集合を {\cal T}=\{a_1,\ldots,a_T\} とする．
X_1,\ldots,X_n をアルファベット集合{\cal T}から選び文字列 x_1x_2\cdots x_n を作ることを考える．
ここでアルファベット a_k が選ばれる確率を p_k とする．

このとき，長さ n の文字列を使われているアルファベットのヒストグラムによって分類する理論をタイプ理論という．

タイプクラス

例えば，アルファベットが 0,1 の2文字の長さ n の文字列を考えると，文字 0 の割合と文字 1 の割合は
(0,1)，\left(\dfrac{1}{n},\dfrac{n-1}{n}\right)，\ldots，\left(\dfrac{n-1}{n},\dfrac{1}{n}\right)，(1,0)
の n+1 通りある（これは0,1のデータが合計 n 個の相対ヒストグラムが n+1 種類あるということ）．

このそれぞれをタイプと呼ぶ．あるタイプ P に対して，それに属する文字列の集合を T(P) で表し，タイプクラスと呼ぶ．
例えば 3 文字の文字列に対して 0が1個，1が2個となるタイプの集合は
T(1/3,2/3)=\{011，101，110\}
であり，その要素の個数は |T(1/3,2/3)|={}_3\mbox{C}_1=3 と求めることができる．

タイプクラスのサイズの不等式

T 文字のアルファベットの長さ n 文字の任意のタイプ P に対して，
n 文字のタイプの総数を \# {\cal P}_n として
\dfrac{1}{\# {\cal P}_n} 2^{nH(P)}\leqq |T(P)| \leqq 2^{nH(P)}
（但しエントロピーの底は2）が成立する．

ここでエントロピーの底を e とすると，この不等式は
\dfrac{1}{\# {\cal P}_n} e^{nH(P)}\leqq |T(P)| \leqq e^{nH(P)}
となり，先程述べたように，2文字のアルファベットの長さ n 文字の任意のタイプの総数は \# {\cal P}_n=n+1 だから本問の不等式
\dfrac{1}{n+1} e^{nH(P)}\leqq |T(P)| \leqq e^{nH(P)}
が得られる．

この不等式はタイプの総数 \# {\cal P}_n が
\# {\cal P}_n\leqq (n+1)^T
をみたすことから， \dfrac{1}{(n+1)^T} 2^{nH(P)}\leqq |T(P)| \leqq 2^{nH(P)}
（但しエントロピーの底は2）で紹介されている教科書もある．

何にせよ．本問は

情報理論 -基礎と広がり-

情報理論 -基礎と広がり-

Amazon

の258ページに載っている例11.1.3である

（{}_n\mbox{C}_k を {n\choose k} と書く流儀がある）が元ネタ．証明も有名なので，この本の証明とほぼ同じ証明の載せてしまうことになる（知っていたので）．

2023.02.01記

やその続きにある

も関連している．