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

通信路行列. 各遷移確率は
$$P(Y=X\mid X)=\frac{3}{4}\cdot \frac{3}{4}=\frac{9}{16},P(Y=1-X\mid X)=\frac{3}{4}\cdot \frac{1}{4}=\frac{3}{16},P(Y=\mathrm{e}\mid X)=\frac{1}{4}$$
であり、どちらの入力に対しても同じである。

$H(Y\mid X)$. 入力 $x$ を固定したときの $Y$ の分布は、どの $x$ でも確率 $\left(\frac{9}{16},\frac{3}{16},\frac{1}{4}\right)$ の並べ替えなので、入力分布によらず
$$\begin{array}{rl}H(Y\mid X)& =\frac{9}{16}{\log }_2\frac{16}{9}+\frac{3}{16}{\log }_2\frac{16}{3}+\frac{1}{4}{\log }_{2}4\\ & =\frac{9}{16}(4-2{\log }_{2}3)+\frac{3}{16}(4-{\log }_{2}3)+\frac{1}{2}\\ & =\frac{9}{4}+\frac{3}{4}+\frac{1}{2}-\left(\frac{18}{16}+\frac{3}{16}\right){\log }_{2}3=\frac{7}{2}-\frac{21}{16}{\log }_{2}3.\end{array}$$

$H(Y)$ の最大化. $P(X=1)=q,P(X=0)=1-q(0\le q\le 1)$ とおくと
$$P(Y=\mathrm{e})=\frac{1}{4},P(Y=0)=\frac{9}{16}(1-q)+\frac{3}{16}q,P(Y=1)=\frac{3}{16}(1-q)+\frac{9}{16}q$$
で、$P(Y=0)+P(Y=1)=\frac{3}{4}$ である。$P(Y=0)=\frac{3}{4}r$ とおくと、エントロピーの分解（グループ化則）により
$$H(Y)=h\left(\frac{1}{4}\right)+\frac{3}{4}h(r)$$
となる（$h(t)=-t{\log }_{2}t-(1-t){\log }_2(1-t)$ は 2 値エントロピー関数）。$h(r)$ は $r=\frac{1}{2}$ で最大値 $1$ をとり、$r=\frac{1}{2}$ は $\frac{9}{16}(1-q)+\frac{3}{16}q=\frac{3}{8}$、すなわち $q=\frac{1}{2}$ のとき実現される。$H(Y\mid X)$ は $q$ によらないので、$I(X;Y)=H(Y)-H(Y\mid X)$ は $q=\frac{1}{2}$ で最大になる。

このとき $Y$ の分布は $\left(\frac{3}{8},\frac{3}{8},\frac{1}{4}\right)$ で
$$H(Y)=2\cdot \frac{3}{8}{\log }_2\frac{8}{3}+\frac{1}{4}{\log }_{2}4=\frac{3}{4}(3-{\log }_{2}3)+\frac{1}{2}=\frac{11}{4}-\frac{3}{4}{\log }_{2}3.$$

通信路容量.
$$C=\frac{11}{4}-\frac{3}{4}{\log }_{2}3-\left(\frac{7}{2}-\frac{21}{16}{\log }_{2}3\right)=\frac{9}{16}{\log }_{2}3-\frac{3}{4}.$$

（別解: 消失確率 $\epsilon$、消失しなかったときの反転確率 $\delta$ のこの通信路の容量は $C=(1-\epsilon )(1-h(\delta ))$ と書ける。$\epsilon =\delta =\frac{1}{4}$、$h\left(\frac{1}{4}\right)=2-\frac{3}{4}{\log }_{2}3$ を代入すると $C=\frac{3}{4}\left(\frac{3}{4}{\log }_{2}3-1\right)$ となり、一致する。）

数値では $C\approx 0.1415$ ビットである。

消失確率を $\epsilon =\frac{1}{4}$、消失しなかったときの反転確率を $p=\frac{1}{4}$ とおく。$E$ を「消失が起こったか」を表す確率変数（$Y=\mathrm{e}$ かどうかで $Y$ から分かる）とすると、$E$ は $X$ と独立で、$E$ は $Y$ の関数である。\n\n$I(X;Y)=H(Y)-H(Y|X)$。\n\n$H(Y|X)$: 各 $x$ について $Y$ の条件付き分布は $(\mathrm{e}:\frac{1}{4},x:\frac{3}{4}\cdot \frac{3}{4}=\frac{9}{16},1-x:\frac{3}{4}\cdot \frac{1}{4}=\frac{3}{16})$。これは $H(E)+(1-\epsilon )h(p)$ に等しい（$h$ は 2 値エントロピー関数）。\n\n$H(Y)$: $P(X=1)=q$ とすると $H(Y)=H(E)+(1-\epsilon )H(Y|E=0)$ で、消失なしのとき $Y$ が 1 である確率は $q(1-p)+(1-q)p$ なので $H(Y|E=0)=h(q(1-p)+(1-q)p)\le 1$。等号は $q=\frac{1}{2}$（一様入力）のとき成立する。\n\nゆえに $I(X;Y)=(1-\epsilon )\{h(q\ast p)-h(p)\}$ であり、最大値は $q=\frac{1}{2}$ で\n$C=(1-\epsilon )(1-h(p))=\frac{3}{4}(1-h(\frac{1}{4}))$。\n\n$h(\frac{1}{4})=\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$。\n\nよって $1-h(\frac{1}{4})=\frac{3}{4}{\log }_{2}3-1$ で、\n$C=\frac{3}{4}\left(\frac{3}{4}{\log }_{2}3-1\right)=\frac{9}{16}{\log }_{2}3-\frac{3}{4}$。\n\n検算: ${\log }_{2}3\approx 1.58496$ より $h(\frac{1}{4})\approx 0.81128$、$C\approx 0.75\times 0.18872=0.14154$。一方 $\frac{9}{16}\times 1.58496-0.75\approx 0.89154-0.75=0.14154$ で一致する。