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

手順 1：出力 $Y$ の分布を $q$ で表す。
$$P(Y=0)=(1-q)\cdot \frac{1}{2}+q\cdot \frac{1}{4}=\frac{1}{2}-\frac{q}{4},$$
$$P(Y=1)=(1-q)\cdot \frac{1}{4}+q\cdot \frac{1}{4}=\frac{1}{4},$$
$$P(Y=2)=(1-q)\cdot \frac{1}{4}+q\cdot \frac{1}{2}=\frac{1}{4}+\frac{q}{4}.$$

手順 2：$H(Y\mid X)$ を求める。
$X=0$ のときも $X=1$ のときも、$Y$ の条件付き分布は確率 $\frac{1}{2},\frac{1}{4},\frac{1}{4}$ の並べ替えなので
$$H(Y\mid X=0)=H(Y\mid X=1)=\frac{1}{2}{\log }_{2}2+\frac{1}{4}{\log }_{2}4+\frac{1}{4}{\log }_{2}4=\frac{1}{2}+\frac{1}{2}+\frac{1}{2}=\frac{3}{2}.$$
よって $H(Y\mid X)=(1-q)\cdot \frac{3}{2}+q\cdot \frac{3}{2}=\frac{3}{2}$ で、$q$ によらない。

手順 3：$I(X;Y)$ を $q$ の関数として表す。
$p_0=\frac{1}{2}-\frac{q}{4}$, $p_2=\frac{1}{4}+\frac{q}{4}$ とおくと
$$I(q)=H(Y)-H(Y\mid X)=-p_0{\log }_2{p}_0-\frac{1}{4}{\log }_2\frac{1}{4}-p_2{\log }_2{p}_2-\frac{3}{2}.$$

手順 4：微分して増減を調べる。
$f$ が $q$ の関数のとき $\frac{d}{dq}\left(-f{\log }_{2}f\right)=-f^{\prime }\left({\log }_{2}f+\frac{1}{\log 2}\right)$ である。$p_0^{\prime }=-\frac{1}{4}$, $p_2^{\prime }=\frac{1}{4}$ だから
$$I^{\prime }(q)=\frac{1}{4}\left({\log }_2{p}_0+\frac{1}{\log 2}\right)-\frac{1}{4}\left({\log }_2{p}_2+\frac{1}{\log 2}\right)=\frac{1}{4}\left({\log }_2{p}_0-{\log }_2{p}_2\right).$$
${\log }_2$ は増加関数なので、$I^{\prime }(q)>0⟺p_0>p_2⟺\frac{1}{2}-\frac{q}{4}>\frac{1}{4}+\frac{q}{4}⟺q<\frac{1}{2}$ である。同様に $q>\frac{1}{2}$ で $I^{\prime }(q)<0$。したがって $I(q)$ は $q=\frac{1}{2}$ で最大となる。

手順 5：最大値を計算する。
$q=\frac{1}{2}$ のとき $P(Y=0)=\frac{3}{8}$, $P(Y=1)=\frac{1}{4}$, $P(Y=2)=\frac{3}{8}$ なので
$$H(Y)=2\cdot \frac{3}{8}{\log }_2\frac{8}{3}+\frac{1}{4}{\log }_{2}4=\frac{3}{4}\left(3-{\log }_{2}3\right)+\frac{1}{2}=\frac{11}{4}-\frac{3}{4}{\log }_{2}3.$$
よって
$$C=\frac{11}{4}-\frac{3}{4}{\log }_{2}3-\frac{3}{2}=\frac{5}{4}-\frac{3}{4}{\log }_{2}3(\approx 0.061)\text{ビット}.$$

通信路行列の各行の確率は $(1/2,1/4,1/4)$ と $(1/4,1/4,1/2)$ で、どちらも並べ替えれば同じ集合なので、$H(Y|X=x)$ は $x$ によらず一定である。

$H(Y|X=x)=\frac{1}{2}\cdot 1+\frac{1}{4}\cdot 2+\frac{1}{4}\cdot 2=\frac{3}{2}$ ビット。よって $H(Y|X)=\frac{3}{2}$。

出力分布は次のとおり。
$P(Y=0)=\frac{1-q}{2}+\frac{q}{4}=\frac{1}{2}-\frac{q}{4}$
$P(Y=1)=\frac{1}{4}$
$P(Y=2)=\frac{1-q}{4}+\frac{q}{2}=\frac{1}{4}+\frac{q}{4}$

相互情報量は
$I(q)=H\left(\frac{1}{2}-\frac{q}{4},\frac{1}{4},\frac{1}{4}+\frac{q}{4}\right)-\frac{3}{2}$。

$P(Y=1)=\frac{1}{4}$ は固定で、$P(Y=0)+P(Y=2)=\frac{3}{4}$ である。この和が一定のもとでは、$P(Y=0)=P(Y=2)=\frac{3}{8}$ のときエントロピーが最大になる。これは $q=\frac{1}{2}$ に対応し、実現可能である。

そのとき
$H(Y)=\frac{1}{4}{\log }_{2}4+2\cdot \frac{3}{8}{\log }_2\frac{8}{3}=\frac{1}{2}+\frac{3}{4}(3-{\log }_{2}3)=\frac{11}{4}-\frac{3}{4}{\log }_{2}3$。

したがって
$C=\frac{11}{4}-\frac{3}{4}{\log }_{2}3-\frac{3}{2}=\frac{5}{4}-\frac{3}{4}{\log }_{2}3\approx 0.0613$ ビット。

検算：${\log }_{2}3\approx 1.58496$ なので $\frac{3}{4}{\log }_{2}3\approx 1.18872$、$C\approx 0.06128$。$q=0$ のときは $H(1/2,1/4,1/4)-1.5=0$ で、$q=1/2$ の値のほうが大きいので整合する。