情報理論・符号理論の問題

1. 合成通信路を求める。

$X=0$ のとき、$1$ 段目で必ず $Y=0$ となり、$2$ 段目でも必ず $Z=0$ となる。よって $P(Z=0\mid X=0)=1$ である。

$X=1$ のとき、$Z=1$ となるのは $1$ 段目で $Y=1$（確率 $\frac{1}{2}$）かつ $2$ 段目で $Z=1$（確率 $\frac{1}{2}$）となる場合だけである。$2$ 段の誤りは独立なので
$$P(Z=1\mid X=1)=\frac{1}{2}\cdot \frac{1}{2}=\frac{1}{4},P(Z=0\mid X=1)=\frac{3}{4}$$
となる。以下 $s=\frac{1}{4}$ とおく。

2. 相互情報量を入力分布で表す。

$P(X=1)=q(0\le q\le 1)$ とし、二値エントロピー関数を $h(t)=-t{\log }_{2}t-(1-t){\log }_2(1-t)$ とする。

$P(Z=1)=qs$ なので $H(Z)=h(qs)$ である。

条件付きエントロピーは、$X=0$ のとき出力が確定するので $H(Z\mid X=0)=0$、$X=1$ のとき $H(Z\mid X=1)=h(s)$ である。よって $H(Z\mid X)=qh(s)$ となり、
$$I(X;Z)=H(Z)-H(Z\mid X)=h(qs)-qh(s)$$
である。

3. 最大化する。

$h$ は凹関数なので $h(qs)$ は $q$ について凹である。$qh(s)$ は $q$ の $1$ 次式なので、$I$ は $q$ の凹関数であり、停留点で最大となる。

$h^{\prime }(t)={\log }_2\frac{1-t}{t}$ より
$$\frac{dI}{dq}=s{\log }_2\frac{1-qs}{qs}-h(s)=0$$
となる。$u=qs$ とおくと ${\log }_2\frac{1-u}{u}=\frac{h(s)}{s}$ である。

ここで
$$h\left(\frac{1}{4}\right)=\frac{1}{4}{\log }_{2}4+\frac{3}{4}{\log }_2\frac{4}{3}=\frac{1}{2}+\frac{3}{4}(2-{\log }_{2}3)=2-\frac{3}{4}{\log }_{2}3$$
なので
$$\frac{h(s)}{s}=8-3{\log }_{2}3={\log }_2\frac{256}{27}$$
となる。したがって
$$\frac{1-u}{u}=\frac{256}{27},u=\frac{27}{283}$$
であり、$q=4u=\frac{108}{283}$ は $0\le q\le 1$ を満たす。

4. 最大値を計算する。

$A={\log }_2\frac{1-u}{u}$ とおくと
$$h(u)=-u{\log }_{2}u-(1-u){\log }_2(1-u)=uA-{\log }_2(1-u)$$
と書ける。停留点では $qh(s)=\frac{u}{s}h(s)=uA$ であるから
$$C=h(u)-uA=-{\log }_2(1-u)=-{\log }_2\frac{256}{283}={\log }_2\frac{283}{256}$$
となる。数値では約 $0.144$ ビットである。

（参考：$1-s=\frac{3}{4}$ を用いた $Z$ 通信路の容量公式 ${\log }_2\left(1+s(1-s{)}^{(1-s)/s}\right)={\log }_2\left(1+\frac{1}{4}\cdot \frac{27}{64}\right)$ とも一致する。）

答え：$C={\log }_2\frac{283}{256}$

1段目で入力 $1$ が正しく出力される確率は $1/2$、2段目でも同様なので、$X\to Z$ の通信路 $W^{(2)}$ は次のようになる。
$W^{(2)}(0|0)=1$, $W^{(2)}(1|0)=0$, $W^{(2)}(1|1)=\frac{1}{2}\cdot \frac{1}{2}=\frac{1}{4}$, $W^{(2)}(0|1)=\frac{3}{4}$。
これは $1\to 0$ の誤り確率が $p=\frac{3}{4}$ の Z 通信路である。

$P(X=1)=a$ とおくと $P(Z=1)=a/4$。$H(Z|X)=ah(1/4)$ なので
$I(X;Z)=h(a/4)-ah(1/4)$。ここで $h$ は2進エントロピー関数である。

$s=a/4$ とおくと $I=h(s)-4sh(1/4)$ となる。
$I$ を $s$ で微分して $0$ とおくと ${\log }_2\frac{1-s}{s}=4h(1/4)$、すなわち $s=\frac{1}{1+2^{4h(1/4)}}$ を得る。

Z 通信路の容量の公式 $C={\log }_2\left(1+(1-p)p^{p/(1-p)}\right)$ に $p=\frac{3}{4}$ を代入する。
$(1-p)p^{p/(1-p)}=\frac{1}{4}{\left(\frac{3}{4}\right)}^3=\frac{27}{256}$
よって $C={\log }_2\left(1+\frac{27}{256}\right)={\log }_2\frac{283}{256}={\log }_{2}283-8\approx 0.144$。

検算：$h(1/4)\approx 0.8113$ から $2^{4h(1/4)}\approx 9.46$、$s\approx 0.0956$、$a\approx 0.382$ となる。
このとき $h(0.0956)\approx 0.4552$、$ah(1/4)\approx 0.3099$ なので $I\approx 0.145$ で、上の値と丸め誤差の範囲で一致する。