九大 システム情報科学府 情報理工学専攻 専門科目（情報系4分野） 2023年度 院試 過去問 解答例・解説（全4問）

以下では離散エントロピーはビット単位、すなわち $\log_2$ を用いる。微分エントロピーも同じ底で書く。

問1

1. $X$ が $[0,a]$ 上の一様分布に従うとき、密度は $f(x)=1/a$ である。したがって $$h(X)=-\int_0^a \frac{1}{a}\log_2 \frac{1}{a}\,dx = \log_2 a .$$
2. $X$ の密度が $f(x)=2x/a^2$ のとき、 $$h(X)=-\int_0^a \frac{2x}{a^2}\log_2 \frac{2x}{a^2}\,dx .$$ $x=ay$ と置くと、$Y=X/a$ の密度は $g(y)=2y$ $(0\le y\le 1)$ であり、 $$h(X)=h(Y)+\log_2 a .$$ ここで $$h(Y)=-\int_0^1 2y\log_2(2y)\,dy = -1-\int_0^1 2y\log_2 y\,dy = -1+\frac{1}{2\ln 2}.$$ よって $$h(X)=\log_2 a -1+\frac{1}{2\ln 2}.$$

問2

誤り源の状態を $0,1$ とする。遷移確率は $$P= \begin{pmatrix} 3/4 & 1/4\\ 1/2 & 1/2 \end{pmatrix}$$ である。定常分布を $\pi=(\pi_0,\pi_1)$ とおくと、$\pi=\pi P$ と $\pi_0+\pi_1=1$ より $$\pi_1=\frac{1}{4}\pi_0+\frac{1}{2}\pi_1,\qquad \pi_0+\pi_1=1 .$$ したがって $$\pi_0=\frac{2}{3},\qquad \pi_1=\frac{1}{3}.$$

2元エントロピー関数を $$h_2(p)=-p\log_2 p-(1-p)\log_2(1-p)$$ と書くと、1次定常マルコフ情報源のエントロピーレートは $$H(S_E)=\sum_z \pi_z H(Z_{t+1}\mid Z_t=z) =\frac{2}{3}h_2\!\left(\frac{1}{4}\right) +\frac{1}{3}h_2\!\left(\frac{1}{2}\right).$$ よって $$H(S_E)=\frac{2}{3}h_2\!\left(\frac{1}{4}\right)+\frac{1}{3} \simeq 0.874\quad\text{bits/symbol}.$$

次に、$z^n$ を固定する。$Y^n=X^n\oplus z^n$ は $X^n$ に対する全単射である。任意の $y^n\in\{0,1\}^n$ に対し、ただ一つの $x^n=y^n\oplus z^n$ が対応するので、 $$P(Y^n=y^n)=P(X^n=y^n\oplus z^n)=2^{-n}.$$ したがって $Y_1,\ldots,Y_n$ は独立同分布で、各時刻で $P(Y_t=1)=1/2$ である。

最後に容量を求める。$Z^n$ は入力と独立で、$Y^n=X^n\oplus Z^n$ であるから $$I(X^n;Y^n)=H(Y^n)-H(Y^n\mid X^n) =H(Y^n)-H(Z^n).$$ ここで $H(Y^n)\le n$ なので $$\frac{1}{n}I(X^n;Y^n)\le 1-\frac{1}{n}H(Z^n).$$ $n\to\infty$ とすると上界は $1-H(S_E)$ である。一方、入力を独立一様にすれば、上で示した全単射性により $Y^n$ も一様になり、$H(Y^n)=n$ が達成される。したがって $$C=1-H(S_E).$$