今回のレポートの内容は、以前に習ったことも使う問題が多く、これまでの理解度のチェックになったかと思います。 勘違いして覚えている人もある程度いるようなので、コメントのよくあった間違いが自分に当てはまらないか、よくチェックしましょう。
答えが等確率の分布\((w_0,w_1,w_2)=\left(\frac{1}{3},\frac{1}{3},\frac{1}{3}\right)\)になった人は不正解です。 定常分布が何故か等確率になることが多いと思っている人は、式の立て方が間違っている人です。 遷移確率行列\(\Pi\)の\((i,j)\)成分\(\Pi_{i,j}\)は、現在の状態が\(S_i\)のとき、次の時刻に状態\(S_j\)へ遷移する確率です。 この遷移確率行列を用いた場合、現在の状態分布\((w_0,w_1,w_2)\)であるときに、次の時刻の状態分布は \[ (w_0,w_1,w_2)\Pi=(w_0\Pi_{0,0}+w_1\Pi_{1,0}+w_2\Pi_{2,0},w_0\Pi_{0,1}+w_1\Pi_{1,1}+w_2\Pi_{2,1},w_0\Pi_{0,2}+w_1\Pi_{1,2}+w_2\Pi_{2,2}) \] となるので定常状態では \[ \left\{\begin{array}{l}w_0\Pi_{0,0}+w_1\Pi_{1,0}+w_2\Pi_{2,0}=w_0\\ w_0\Pi_{0,1}+w_1\Pi_{1,1}+w_2\Pi_{2,1}=w_1\\ w_0\Pi_{0,2}+w_1\Pi_{1,2}+w_2\Pi_{2,2}=w_2\end{array}\right.\] となります。この連立方程式が違っている人がいます。何故違ってしまうかというと、行ベクトルに遷移確率行列を右からかけていない、または行列計算が正しくできないためと考えられます。 遷移確率行列を考えなくても式は立てることができます。 時刻\(t\)の状態を\(Q_t\)とおけば、 \[ \begin{eqnarray*}P(Q_{t+1}=S_i)&=&P(Q_{t+1}=S_i,Q_t=S_0)+P(Q_{t+1}=S_i,Q_t=S_1)+P(Q_{t+1}=S_i,Q_t=S_2)\\ &=&P(Q_t=S_0)P(Q_{t+1}=S_i|Q_t=S_0)+P(Q_t=S_1)P(Q_{t+1}=S_i|Q_t=S_1)+P(Q_t=S_2)P(Q_{t+1}=S_i|Q_t=S_2)\end{eqnarray*}\] が成り立ちます。定常状態では\(P(Q_{t+1}=S_i)=P(Q_t=S_i)=w_i\)であることから式を立てることができます。
ビット誤り率は誤り源\(S_E\)から1が発生する確率です。 状態\(S_0\)で１が発生する確率は\(\frac{1}{2}\)、状態\(S_1\)で１が発生する確率は\(\frac{1}{16}\)、状態\(S_2\)で１が発生する確率は\(\frac{1}{2}\)です。 ですから答えは、\(w_0\times \frac{1}{2}+w_1\times \frac{1}{16}+w_0\times \frac{1}{2}\)を計算した値となります。
マルコフ情報源のエントロピーの計算式はスライドや教科書で確認しておいてください。 式は近いのだけど違っているパターンとしては、\(H(E|S_i)\)の計算の仕方を値ごとではなくて遷移ごと(矢印ごと)に行なっている人が数名いました。 例えば\(H(E|S_1)\)は、状態\(S_1\)にいる場合の確率分布\((P_{S_1}(E=0),P_{S_1}(E=1))=\left(\frac{15}{16},\frac{1}{16}\right)\)で決まり、 \(H(E|S_1)=\mathcal{H}\left(\frac{1}{16}\right)\)となります。これを遷移ごとに計算すると\(H(E|S_1)=-\frac{1}{16}\log_2\frac{1}{16} -\frac{7}{8}\log_2\frac{7}{8} -\frac{1}{16}\log_2\frac{1}{16}\)となり、計算が面倒になり間違った値がでます。また正しい計算をした人でもエントロピー関数値\(\mathcal{H}\left(\frac{1}{16}\right)\)の計算が間違っている人がいました。エントロピー関数\(\mathcal{H}(x)\)は、 \(\mathcal{H}(x)=-x\log_2 x-(1-x)\log_2 (1-x)\)と定義されますが、\(\mathcal{H}(x)=-x\log_2 x\)で計算している人が数人いました。この間違いは計算を簡単にしますが、答えは間違いです。また、今回エントロピー関数表を載せたのですが\(\mathcal{H}\left(\frac{1}{16}\right)\)にぴったりの欄がなくて、正しく計算した人も困ったのではないかと思います。ただ、\(\frac{1}{16}=0.0625\)であるので、近い値として\(\mathcal{H}(0.06)\)を引いてくれた人がいましたが、それで良いと思います。また、定義式に戻って\(\log\)の計算で頑張って出した人もいました。これも良いですね。期末演習などで表を利用して解く指示の場合は、表から引けるように気をつけます。
この問題は、ビット誤り率が同じ場合には、記憶のある通信路の方が通信路容量が大きくなることを確かめる問題です。 比較した結果、記憶のない通信路(２元対称通信路)の方が記憶のある通信路（誤り源がマルコフ情報源の加法的２元通信路)より通信路容量が大きくなってしまった人は、どこか間違っている人です。 ビット誤り率\(p\)が問１のマルコフ情報源のビット誤り率\(\frac{3}{20}\)と等しい場合の通信路容量\(C=1-\mathcal{H}(\frac{3}{20})\)の計算は、エントロピー関数表より簡単に求まりますね。
今回はちょっと分かりにくい内容だったので、例題で説明をしましたが、大学の専門教育ではそのような受験勉強的な説明はあまり行いません。概念や定義の理解を深めるために、自分で調べなから解ける力をつけることが重要だと思います。
解答例はあげませんが、よくある間違いを上に載せました。自分の解答が当てはまっていないかチェックしておいてください。
わからないことがあったらスラックで質問してください。
確かにエントロピー関数の記号とエントロピーの記号は見分けが難しいですね。エントロピー関数の記号は世界共通のものは特にないので、 好きな記号で自分で定義してから使っても良いと思います。最近のワードの場合は、数式モードで花文字記号が使えるので、それを使うのも良いと思います。
諦めずに勉強しましょう。
素晴らしいですね。どこかて必ず役に立つと思います。
2021.7.30 作成，担当：中村