情報理論

対数は凹関数なので、「平均的に」その接線の下側にある。ギブスの不等式は、凹関数 $\log_2$ に $p$ で重み付けしたイェンセンの不等式そのものである：対数の中の各比 $q_i/p_i$ をその $p$ 重み付き平均（$1$ に等しい）で置き換えると和は増加するしかなく、そのため情報量は非負にならざるを得ない。

すべての $x > 0$ に対する初等的な不等式 $\ln x \le x - 1$ から始める。等号は $x=1$ のときのみ成立する（これは $f(x) = \ln x - (x-1)$ が $f(1)=0$、$f'(x) = 1/x - 1$ を持ち、$x<1$ で正、$x>1$ で負であるため、$f$ が $x=1$ に唯一の最大値を持つことからわかる）。$\ln 2$ で割ると $\log_2 x \le (x-1)/\ln 2$ となる。

これを各 $i$ について $x = q_i/p_i$ に適用する：$\log_2(q_i/p_i) \le (q_i/p_i - 1)/\ln 2$。両辺に $p_i > 0$ を掛け（不等号の向きは変わらない）、$i$ について和をとる：$\sum_i p_i \log_2(q_i/p_i) \le \frac{1}{\ln 2}\sum_i (q_i - p_i) = \frac{1}{\ln 2}\left(\sum_i q_i - \sum_i p_i\right) = \frac{1}{\ln 2}(1 - 1) = 0$、なぜなら $p$ と $q$ はどちらも和が $1$ の確率分布だからである。

左辺はまさに $-D(p\|q)$ である（対数の中身が $p_i/q_i$ ではなく $q_i/p_i$ であることによる符号の反転に注意）ので、これは $D(p\|q) \ge 0$ を証明する。

すべてで等号が成り立つには、$p_i > 0$ であるすべての $i$ について $\ln x \le x-1$ で等号が必要であり、それはそのようなすべての $i$ で $q_i/p_i = 1$ のとき、すなわち $p = q$ のときにのみ起こる。

下限は、エントロピーが厳格な下限であることを示している：どの可逆な接頭符号も、平均して記号あたり $H(X)$ ビットを下回ることはできない。それを上回るには、符号によって誘導される分布が $X$ の真の分布と異なる必要があり、それはギブスの不等式が禁じているからである。上限は、この下限がほぼ達成可能であることを示している：各理想長 $-\log_2 p_i$ を整数に切り上げても、平均して1ビット未満しか無駄にならない。

下限については、$l_i$ を任意の接頭符号の長さとすると $\sum_{i=1}^n 2^{-l_i} \le 1$ が成り立つ。$Z=\sum_j 2^{-l_j} \le 1$ として $q_i = 2^{-l_i}/Z$ と定義すると、$q$ は確率分布になる。ギブスの不等式より、$0 \le D(p\|q) = \sum_i p_i \log_2(p_i/q_i) = \sum_i p_i\log_2 p_i - \sum_i p_i \log_2(2^{-l_i}/Z) = -H(X) + \sum_i p_i l_i + \log_2 Z$。$Z \le 1$ より $\log_2 Z \le 0$ なので、$0 \le -H(X) + L + \log_2 Z \le -H(X) + L$ となり、これを整理すると $L \ge H(X)$ が得られる。

上限（達成可能性）については、各 $i$ に対して $l_i = \lceil -\log_2 p_i \rceil$ を選ぶ（理想長を最も近い整数に切り上げる）。この長さはクラフトの不等式を満たす。なぜなら $2^{-l_i} \le 2^{-(-\log_2 p_i)} = p_i$ なので $\sum_i 2^{-l_i} \le \sum_i p_i = 1$ となるからである。クラフト・マクミラン構成により、このような長さは常に実際の接頭符号として実現できる（2分木の中でレベルごとに2進文字列を割り当てて符号を構築する）。

天井関数の定義より $l_i < -\log_2 p_i + 1$。これに $p_i \ge 0$ を掛けて $i$ について和をとると $L = \sum_i p_i l_i < \sum_i p_i(-\log_2 p_i + 1) = H(X) + 1$ となる。

両方を合わせると、この構成は $H(X) \le L < H(X) + 1$ を達成する。

容量は単に便利な公式であるだけでなく、真の壁である。その値より下では、十分に長いブロックにメッセージを広げることで、ランダムに見える符号語が雑音があっても区別可能なままとなり、誤りを0に近づけることができる。その値より上では、どんなに巧妙な符号を使っても、通信路は符号が保護できる速さよりも速く情報を破壊してしまう。

**逆方向（$R > C \Rightarrow P_e \not\to 0$）。** ファノの不等式は、雑音のある出力が与えられたときの受信者のメッセージに関する残存不確実性を次のように抑える：$H(X\mid Y) \le 1 + P_e \log_2(n-1)$、ここで $n$ は可能なメッセージ数である。一方、通信路のデータ処理構造により各使用ごとに $I(X;Y) \le C$ が強制されるため、$N$ 回の通信路使用のブロック全体で受信者が抽出できる情報は高々 $NC$ ビットである。真のレートが $R > C$（1使用あたり）であれば、メッセージは $NR$ ビットのエントロピーを持つが、通信路はそのうち約 $NC < NR$ ビットしか提供しない。ファノの不等式は、$N$ が大きくなっても $P_e$ が $0$ から離れたままであることを強制する。なぜなら残存不確実性 $H(X\mid Y)$ を消し去ることができないからである。

**達成可能性の概略（$R < C \Rightarrow P_e \to 0$）。** 容量を達成する入力分布 $p(x)$ を固定し、長さ $N$ の符号語 $2^{NR}$ 個を $p(x)^N$ から独立にランダムに生成して符号帳を作る。復号の際、受信者は受信系列と同時典型的（統計的パターンが真の入力・出力対のように振る舞う）である唯一の符号語を探す。$R < C$ であるため、候補符号語の数（$2^{NR}$）は統計的に区別可能な通信路出力の数（$\approx 2^{NC}$）よりはるかに少なく、$N \to \infty$ のとき、送信されていない他の符号語が偶然受信系列と同時典型的に見える確率は $0$ に縮小し、復号誤り確率も、符号帳のランダムな選択について平均すると同様に縮小する — したがって、任意に小さい $P_e$ を達成する符号帳が少なくとも1つ存在するはずである。