ChunPom’s diary

数学、物理、機械学習に関する話題。あと院試、資格、大学入試まで。

大学入試数学良問2-エントロピーの上限値-

大学入試 数学 良問

「 { \displaystyle x_i(i=1,2,...,n)} を正の数とし, { \displaystyle \sum_{i=1}^{n}x_i=k} を満たすとする。このとき、
不等式 { \displaystyle \sum_{i=1}^{n}x_i \log{x_i} \geq k\log{\frac{k}{n}}} を求めよ。」
(東工大前期1990)

この問題は、後述するように”エントロピー”に対する不等式に関する問題である。
以下、考え方兼略解。

考え方のポイントは、
①凸関数の構造に気付けるか
②帰納法を選択できるか
の2つ。

では、略解を記載する。
まずは、 { \displaystyle n} で割った { \displaystyle \frac{1}{n}\sum_{i=1}^{n}x_i \log{x_i} \geq \frac{k}{n}\log{\frac{k}{n}}} の両辺を詳しく見る。式の構造として、左辺にも右辺にも” { \displaystyle A\log{A}}"が現れていることがわかる。そして左辺はそれに各値を代入したものの平均値、右辺は各値の総和を一括して代入したものになっている。このような性質は、何も” { \displaystyle A\log{A}}"に限った話ではなく、下に凸な関数では常に成り立つ性質である。
よってこの性質を帰納法で証明しよう。
すなわち下に凸な関数に対し、 { \displaystyle f\left(\frac{x_1+x_2+\cdots+x_n}{n}\right)\leq \frac{1}{n}\{f(x_1)+f(x_2)+\cdots+f(x_n)\}}
(等号成立は { \displaystyle x_1=x_2=\cdots=x_n} の時)を示す。

{ \displaystyle n=1} の時は明らか。
{ \displaystyle n=k\ (k=1,2,...)} の時に { \displaystyle f\left(\frac{x_1+x_2+\cdots+x_k}{k}\right)\leq \frac{1}{k}\{f(x_1)+f(x_2)+\cdots+f(x_k)\}}
(等号成立は { \displaystyle x_1=x_2=\cdots=x_k} の時)が成り立つと仮定する。
{ \displaystyle n=k+1} を考えると、
\begin{eqnarray*} f\left(\frac{x_1+x_2+\cdots+x_k}{k+1}\right)&=& f\left(\frac{k}{k+1}\frac{x_1+x_2+\cdots+x_k}{k}+\frac{x_{k+1}}{k+1}\right)\\
&\leq&\frac{k}{k+1}f\left(\frac{x_1+x_2+\cdots+x_k}{k}\right)+\frac{1}{k+1}f\left(x_{k+1}\right)\\
&\leq&\frac{k}{k+1}\frac{f(x_1)+f(x_2)+\cdots+f(x_k)}{k}+\frac{1}{k+1}f\left(x_{k+1}\right)\\
&=&\frac{1}{k+1}\{f(x_1)+f(x_2)\cdots+f(x_k)\}\end{eqnarray*}
が成り立つ。
ここで、二行目では、下に凸な関数の性質である { \displaystyle f(px+qy)\leq p f(x)+q f(y)}
(等号成立は { \displaystyle x= y})を用いた。
また、三行目では { \displaystyle n=k\ (k=1,2,...)} での仮定を用いた。
二行目の等号成立は { \displaystyle (x_1+\cdots+x_k)/k=x_{k+1}}の時、三行目の等号成立にはさらに { \displaystyle x_1=x_2=\cdots=x_k} が課されるため、 { \displaystyle n=k+1} の時の等号成立は { \displaystyle x_1=x_2=\cdots=x_{k+1}} となる。
以上より、帰納法的に { \displaystyle f\left(\frac{x_1+x_2+\cdots+x_n}{n}\right)\leq \frac{1}{n}\{f(x_1)+f(x_2)+\cdots+f(x_n)\}} (等号成立は { \displaystyle x_1=x_2=\cdots=x_n} の時)が示された。

実際、 { \displaystyle x\log{x}\ (x\geq 0)} は二回微分して正になるため、下に凸の関数であり、上式を満たすことから、題意の式は示される。

ちなみに、本問題はエントロピーの上限を与える式と言える。
(シャノン)エントロピーとは系の乱雑さを示す量で、ある確率変数 { \displaystyle X} が事象 { \displaystyle i \ (i=1,2,...,n)} となる確率を { \displaystyle P_i }とすれば、
{ \displaystyle H_{n}(X)=-\sum_{i}^{n} P_i \log{P_i}}
と定義される。
従って、本問題の結果により、確率の和が1であることを用いて整理すると、
{ \displaystyle H_{n}(X)\leq \log{n}}
を得る。
また、最大となる場合は { \displaystyle P_1=P_2=\cdots=P_n=1/n} の時であり、全事象が等確率に出現し、乱雑さが最も大きくなっていることがわかる。
このような分布を、離散一様分布という。
su-butsu-kikaigakusyuu.hatenablog.com