比べる2つの分布：通信路の入力と出力

相対エントロピーから情報と物理を組み立てる　第1部 第6章 §1.6.1　★★★ 通信路は確率行列 $W$。相互情報量は「入力ごとの出力の分布」と「平均の出力の分布」の $D$ の平均になる

雑音のある線を通して文字を送ると、受け手の手元には送った文字と少し違う文字が届くことがある。それでも、同じ内容を工夫して何回かに分けて送れば、誤りの確率をいくらでも小さくできるだろうか。できるとすれば、1回の使用あたり何ビットまでなら送れるだろうか。この章はこの問いに答える。答えの数が通信路容量 $C$ で、Shannon が 1948 年の論文¹1C. E. Shannon (1948), Bell System Technical Journal 27, 379–423, 623–656.下の脚注へ閉じるで定義し、その意味を通信路符号化定理として示した。

この章で比べる2つの分布は、通信路の入力 $X$ と出力 $Y$ の結合分布 $p_{XY}$ と、入力と出力を独立とみなした積 $p_Xp_Y$ である。2つの $D$ が相互情報量 $I(X;Y)=D(p_{XY}\,\|\,p_Xp_Y)$（相対エントロピーから情報と物理を組み立てる 第1部第3章）で、入力の分布を選んでこれを最大にした値が通信路容量 $C$ になる。この章で出てくる結果は4つある。第一に、$C$ は通信路の各入力に対応する出力の分布を点とみなしたとき、それらすべてを含む最小の「$D$ の球」の半径に等しい。この見方から、最適な入力の分布を判定する条件（Kuhn–Tucker の条件）と、容量の上界がすぐに出る。第二に、通信路符号化定理である。送る速さが $C$ より小さければ誤りの確率をいくらでも小さくでき、$C$ を超えると誤りの確率は下から押さえられる。後半（逆定理）は Fano の不等式とデータ処理不等式（相対エントロピーから情報と物理を組み立てる 第1部第4章）から出る。第三に、容量を数値で求める Blahut–Arimoto の反復法である。この反復の各段は $D\ge0$ を2回使った交互の最大化になっている。第四に、連続の値をとる Gauss 通信路の容量 $C=\frac12\ln(1+P/N)$ と、熱雑音のもとで1ビットを送るのに要るエネルギーの下限 $k_{\mathrm B} T\ln2$ である。

この章では対数は自然対数で、情報量の単位は nat である。ビットで述べる所だけ $\log_2$ と書くか、nat の値を $\ln2$ で割って「ビット」と添える（1 ビット $=\ln2$ nat）。

離散無記憶通信路

この章では $x$ を送ったときの出力の分布 $W(\cdot\,|\,x)$ を $W_x$ と略して書く。$W_x$ は $\mathcal Y$ 上の確率分布で、行列 $W$ の第 $x$ 行にあたる。代表的な通信路を3つ挙げる（図 1.6.1）。

• 2元対称通信路 BSC($\varepsilon$)：$\mathcal X=\mathcal Y=\{0,1\}$ で、送った文字が確率 $\varepsilon$ で反転する。
• 2元消失通信路 BEC($\varepsilon$)：$\mathcal X=\{0,1\}$、$\mathcal Y=\{0,\mathrm e,1\}$ で、確率 $\varepsilon$ で文字が消えて記号 $\mathrm e$（消失）が届き、それ以外は正しく届く。
• Z 通信路 Z($s$)：$0$ は必ず $0$ として届き、$1$ は確率 $s$ で $0$ に化ける。光の有無で $0$ と $1$ を送り、光子を取り逃がすことがあっても光の無い所に光子を数えることはない受信器が、この形になる。

相互情報量を行ごとの $D$ に分ける

送り手が入力の文字を分布 $p(x)$ で選ぶと、入力と出力の結合分布と出力の分布は

$$p_{XY}(x,y)=p(x)\,W(y\,|\,x),\qquad q(y)=\sum_{x}p(x)\,W(y\,|\,x)\tag{1.6.2}$$

になる。行列で書けば出力の分布は $q=pW$（行ベクトル $p$ に $W$ を右から掛けたもの）である。相互情報量は、結合分布と、それを独立とみなした積 $p(x)q(y)$ の $D$ だった（相対エントロピーから情報と物理を組み立てる 第1部第3章）。定義に式 (1.6.2) を入れ、$p(x)$ を約すと

$$I(X;Y)=D(p_{XY}\,\|\,p_Xp_Y)=\sum_{x,y}p(x)W(y\,|\,x)\ln\frac{p(x)W(y\,|\,x)}{p(x)q(y)}=\sum_{x}p(x)\,D(W_x\,\|\,q)\tag{1.6.3}$$

となる。$W$ を決めておけば $I(X;Y)$ は入力の分布 $p$ だけの関数なので、この章では $I(p,W)$ とも書く。

式 (1.6.3) の右辺は、入力 $x$ を送ったときの出力の分布 $W_x$ が、平均の出力の分布 $q$ からどれだけ離れているかを $D$ で測り、それを $p(x)$ で平均したものである。受け手は $y$ を見て $x$ を推し量るので、入力ごとの出力の分布が互いに離れているほど、つまり平均 $q$ から離れているほど、$y$ から $x$ を当てやすい。すべての行が同じ分布（$W_x=q$）なら、出力は入力と無関係で、$I=0$ になる。

式 (1.6.3) を $\ln\frac{W(y|x)}{q(y)}=-\ln q(y)+\ln W(y\,|\,x)$ と分けて和をとると、教科書でよく見る形

$$I(p,W)=H(Y)-H(Y\,|\,X)=H(q)-\sum_xp(x)H(W_x)\tag{1.6.4}$$

も出る。$H(Y)$ は出力の不確かさ、$H(Y\,|\,X)$ は入力を知っても残る不確かさ（雑音が足した分）で、その差が入力について分かる量になる。たとえば BSC($0.1$) に入力 $p=(0.7,0.3)$ を入れると $q(1)=0.7\cdot0.1+0.3\cdot0.9=0.34$ で、$I=h_{\mathrm b}(0.34)-h_{\mathrm b}(0.1)\approx0.316$ nat $\approx0.456$ ビットになる。

1　C. E. Shannon (1948), Bell System Technical Journal 27, 379–423, 623–656.