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

マルコフ情報源

状態を $1,2,3$ とし、図から読み取れる遷移確率を $$P=\begin{pmatrix} p&p&1-2p\\ q&q&1-2q\\ 1/2&1/2&0 \end{pmatrix}$$ とおく。定常分布を $\pi=(\pi_1,\pi_2,\pi_3)$ とすると、1列目と2列目が同じ形なので $\pi_1=\pi_2=a$ である。正規化条件と $\pi=\pi P$ から $$a=a(p+q)+\frac{1-2a}{2},\qquad 2a+\pi_3=1.$$ よって $$\pi_1=\pi_2=\frac{1}{2(2-p-q)},\qquad \pi_3=\frac{1-p-q}{2-p-q}.$$

$p=q=r$ のとき、状態1,2の条件付きエントロピーは $$h_r=-2r\log_2 r-(1-2r)\log_2(1-2r)$$ であり、状態3では二つの遷移が $1/2,1/2$ なので条件付きエントロピーは $1$ bit である。したがって $$H(X)=\frac{1}{2(1-r)}h_r+\frac{1-2r}{2(1-r)}.$$ $r=1/3$ では $h_r=\log_2 3=1.58$ なので $$H(X)=\frac34\cdot 1.58+\frac14=1.435\ \text{bit}.$$ $r=1/4$ では行分布が $(1/4,1/4,1/2)$ で $h_r=1.5$ だから $$H(X)=\frac23\cdot 1.5+\frac13=\frac43\ \text{bit}.$$

ハフマン符号

$p(a)=0.9,p(b)=0.1$ である。与えられた近似値を使うと $$H(X_1)=-0.9\log_2 0.9-0.1\log_2 0.1 =0.9(0.16)+0.1(3.32)=0.476\ \text{bit}.$$ $X_1$ に対しては、例えば $a\mapsto0,\ b\mapsto1$ とすれば平均符号長は $1$ bit である。

$X_1X_2$ の確率は $$aa:0.81,\quad ab:0.09,\quad ba:0.09,\quad bb:0.01.$$ ハフマン併合では $0.01+0.09=0.10,\ 0.09+0.10=0.19,\ 0.19+0.81=1$ とできる。例えば $$aa\mapsto0,\quad ab\mapsto10,\quad ba\mapsto110,\quad bb\mapsto111$$ とすれば、平均符号長は $$0.81\cdot1+0.09\cdot2+0.09\cdot3+0.01\cdot3=1.29$$ であり、1文字あたり $0.645$ bit である。

$X_1X_2X_3$ では確率 $0.729$ の $aaa$、確率 $0.081$ の3語、確率 $0.009$ の3語、確率 $0.001$ の $bbb$ がある。ハフマン符号の一例は $$\begin{array}{c|c} aaa&0\\ aab,aba,baa&100,101,110\\ abb,bab,bba,bbb&11100,11101,11110,11111 \end{array}$$ である。この平均符号長は $$0.729\cdot1+3(0.081\cdot3)+4\text{語部分}=1.598$$ すなわち1文字あたり $1.598/3=0.5327$ bit である。