この章のまとめ

(1) $Z\neq X$ となるのは、2段のうちちょうど1段で反転したときで、その確率は $p(1-p)+(1-p)p=2p(1-p)$。どちらの入力でも同じなので BSC($p_2$) である。行列で書けば $W_{X\to Z}=W_{\mathrm{BSC}(p)}W_{\mathrm{BSC}(p)}=W_{\mathrm{BSC}(p_2)}$。$p_2-p=p(1-2p)>0$（$0<p<\frac12$）なので2段のほうが乱れる。$p=0.1$ では $p_2=0.18$。$X\to Y\to Z$ は Markov 連鎖（$Z$ は $Y$ だけを見て作られる）なので、データ処理不等式から入力の分布によらず $I(X;Z)\le I(X;Y)$。

(2) 一様な入力では出力も一様で、$D(W_0\,\|\,\text{一様})=(1-p)\ln\bigl(2(1-p)\bigr)+p\ln(2p)=\ln2-h_{\mathrm b}(p)$、$D(W_1\,\|\,\text{一様})$ も同じ値になる。両方の入力を使い、両方の $D$ が等しいので条件 (1.6.8) を満たし、一様な入力が最適である。

$$C_1=\ln2-h_{\mathrm b}(0.1)\approx0.6931-0.3251=0.3681\ \text{nat}=0.5310\ \text{ビット},$$

$$C_2=\ln2-h_{\mathrm b}(0.18)\approx0.6931-0.4714=0.2218\ \text{nat}=0.3199\ \text{ビット}.$$

$C_2<C_1$ は (1) のデータ処理不等式を容量で言い直したものである。

(3) 式 (1.6.12) をビットで使う。$n=200$ では $P_{\mathrm{err}}\ge1-\frac{0.3199}{0.5}-\frac{1}{200\times0.5}=1-0.640-0.010=0.350$、$n\to\infty$ では $1-0.640=0.360$。1段だけなら $0.5<C_1=0.531$ ビットなので逆定理の右辺は負で何も言わず、順定理から誤りをいくらでも小さくできる。中継点が受け取った文字をそのまま流すと容量が下がるので、速さ $0.5$ ビットは2段では送れない。中継点で一度復号して符号化し直せば、各段を $C_1$ 未満の速さで使えるので、0.5 ビットでも送れる。

(4) 2段の行は $W_0=(0.82,0.18)$、$W_1=(0.18,0.82)$。$q_0=0.8W_0+0.2W_1=(0.692,0.308)$。

$$\begin{aligned}D(W_0\,\|\,q_0)&=0.82\ln\frac{0.82}{0.692}+0.18\ln\frac{0.18}{0.308}\approx0.0425,\\ D(W_1\,\|\,q_0)&=0.18\ln\frac{0.18}{0.692}+0.82\ln\frac{0.82}{0.308}\approx0.5606 .\end{aligned}$$

$L_0=0.8\times0.0425+0.2\times0.5606\approx0.1461$ nat、$U_0=0.5606$ nat で、$C_2=0.2218$ を挟む。更新は

$$\pi_1=\frac{0.2\,\mathrm{e}^{0.5606}}{0.8\,\mathrm{e}^{0.0425}+0.2\,\mathrm{e}^{0.5606}}\approx\frac{0.3503}{0.8347+0.3503}\approx0.2956 .$$

少なく使っていた入力 $1$ は平均の出力から遠いので確率が増え、最適な $\frac12$ へ近づいた。次の段は $L_1\approx0.1871$、$U_1\approx0.4286$ nat で、上下の幅は $0.41$ から $0.24$ に縮む。

(5) 一様な入力では出力 $Z$ も一様で $H(Z)=\ln2$、出力の典型系列はおよそ $\mathrm{e}^{nH(Z)}=2^{1000}$ 個。1つの符号語を送ったときの雲は $\mathrm{e}^{nH(Z|X)}=\mathrm{e}^{nh_{\mathrm b}(0.18)}=2^{1000\times0.6801}\approx2^{680}$ 個。見分けられる符号語の数はおよそ $2^{1000}/2^{680}=2^{320}$ で、指数は $nC_2=1000\times0.3199\approx319.9$ ビットに一致する。

(6) $0<p<\frac12$ なら $|1-2p|<1$ なので $p_k\to\frac12$ で、$C_k=\ln2-h_{\mathrm b}(p_k)\to0$。何段もそのまま流すと、出力は入力についての情報をほとんど持たなくなる（データ処理不等式から $C_k$ は $k$ について単調に減る）。$\delta=(1-2p)^k$ とおくと $p_k=\frac{1-\delta}2$ で、$h_{\mathrm b}\bigl(\frac{1-\delta}2\bigr)$ を $\delta$ で展開すると $\ln2-\frac{\delta^2}{2}+\mathcal{O}(\delta^4)$ なので

$$C_k=\ln2-h_{\mathrm b}(p_k)\approx\frac{\delta^2}{2}=\frac12(1-2p)^{2k}\quad[\text{nat}].$$

$p=0.1$ では $C_5\approx0.055$、$C_{10}\approx0.0058$ nat で、$k=10$ の近似式 $\frac12(0.8)^{20}$ との比は $1.002$ である。容量は段の数について指数関数で $0$ に近づく。