３．マルコフ情報源

生起するシンボル相互間に依存性がある情報源は、マルコフ情報源。

直近$${m}$$個のシンボルに依存し、
次のシンボルが生起する情報源を$${m}$$重マルコフ情報源という。
特に$${m=1}$$のときを単純マルコフ情報源と呼ぶ。

定常分布

マルコフ情報源は、次の方程式を満たす状態分布$${\pi}$$が存在し、
平衡方程式と呼ぶ。

$${\bold\pi \bold P=\pi}$$  （$${P:}$$推移確率行列）

この式は一次独立ではないので、$${\pi}$$は一意に定められない。
したがって、$${\bold\pi 1^{ \mathrm{ T } }=1}$$　　($${\pi_1+\pi_2+\cdot \cdot \cdot +\pi_i =1}$$)を補う。

また、$${\pi}$$の$${j}$$成分$${\pi_j}$$を状態$${q_j}$$の定常確率と呼ぶ。

ビット誤り率

$${0}$$を入力して、$${1}$$が出力。
$${1}$$を入力して、$${0}$$が出力。

このような場合、ビット誤りである。

計算は、定常分布の誤り$${\times}$$定常確率の和
$${q_0 \times P_{01}+q_1 \times P_{10}}$$

マルコフ情報源

単純（$${m=1}$$）マルコフ情報源の図は以下のようになる。
これは何を示しているか？

• 0から0を出力。その（条件付$${^※}$$）確率は、$${P(0|0) =1-q}$$

• 1から0を出力。その（条件付）確率は、$${P(1|0)=p}$$

※前のシンボルの影響を受けるから。

つまり、１つ前の影響を受けて、出力が決まる。
これが単純マルコフ情報である。

単純マルコフ情報源から、0を出力するときの確率。

• 0から0を出力。その確率は、$${P(0|0) =1-q}$$

• 1から0を出力。その確率は、$${P(1|0)=p}$$

0,1の確率をそれぞれ$${w_0,w_1}$$とする。
求める確率$${w_0}$$は、

$${w_0=(1-q)w_0+pw_1}$$
また、$${w_0+w_1=1}$$より

$${w_0=\displaystyle\frac{p}{p+q}}$$

このことは、定常分布方程式を示している。

2重マルコフ情報源は？

• 00から0を出力。$${P(0|00)}$$,

• 10から0を出力。$${P(0|10)}$$

矢印の向きは、必ず図のようになる。
イメージとしては、
2つ連続したシンボルの1つ目が出力シンボルに押し出された
と思い浮かべればよい。

シンボル$${00}$$から1を出力すると、シンボル$${0\bold{01}}$$となる。
２つを記憶するから、初めの1つは手放す。

1重から2重マルコフ情報源の導出

定期テスト（院試）の誘導で問われる。

２つ連続する00を出力する確率を求めよ。

2つのシンボルを記憶しているので、
0と0が連続しているところから、0が出力
1と0が連続しているところから、0が出力

この二つの確率の和が00を出力する確率である。
つまり3つの内、1番目は01どちらでも。2番目は0、3番目は0。

$${P(0|00)=w_0P(0|0)P(0|0)+w_1P(1|0)P(0|0)}$$

エントロピー

$${m}$$重マルコフ情報源$${S=\{s_1,s_2,s_3, \cdot \cdot \cdot,s_J\}}$$のエントロピー$${H(S)}$$は、

$${H(S)=\displaystyle \sum_{i} \pi_i\displaystyle \sum_{j=1}^J P(s_j|q_i)\log\frac{1}{P(s_j|q_i)}}$$

１次エントロピー$${H_1(S)}$$の場合

情報源記号$${\{0,1\}}$$の単純マルコフ情報源を考える。

$${H_1(S)=-(\pi_{\bold 0}P(0|{\bold 0})\log P(0|{\bold 0})+\pi_{\bold 1}P(0|{\bold 1})\log P(0|{\bold 1})+\pi_{\bold 0}P(1|{\bold 0})\log(P(1|{\bold 0}))+\pi_{\bold 1}P(1|{\bold 1})\log P(1|{\bold 1}))}$$  ※太字は目立たせるため

間違わないために、各々確率を計算する。

$${p(0)=\pi_{\bold 0}P(0|{\bold 0})+\pi_{\bold 1}P(0|{\bold 1})}$$
$${p(1)=\pi_{\bold 0}P(1|{\bold 0})+\pi_{\bold 1}P(1|{\bold 1})}$$
$${H_1(S)=-p(0)\log p(0)-p(1)\log p(1)}$$

2次エントロピー$${H_2(S)}$$の場合

m重マルコフ情報源$${S}$$の$${n}$$次拡大$${S^n}$$で、
この項では、2次拡大。

それぞれの確率は$${p(0|0),p(0|1),p(1|0),p(1|1)}$$となる。

$${p(0\bold 0)=(\pi_{\bold 0}P(0|{0})+\pi_{\bold 1}P(0|{1}))\bold{P(0|0)}}$$
$${p(0\bold 1)=(\pi_{\bold 0}P(0|{0})+\pi_{\bold 1}P(0|{ 1}))\bold{P(1|0)}}$$
$${p(1\bold 0)=(\pi_{\bold 0}P(1|{0})+\pi_{1}P(1|{\bold 1}))\bold{P(0|1)}}$$
$${p(1\bold 1)=(\pi_{\bold 0}P(1|{0})+\pi_{\bold 1}P(1|{1}))\bold{P(1|1)}}$$

$${H(S^2)=-(p(00)\log p(00)+p(01)\log p(01)+p(10)\log p(10)+p(11)\log p(11))}$$

$${H(S^2)}$$は、$${\{00\},\{01\}}$$というように２個の出力を１つとして考えている。

$${H(S^n)=nH_n(s)}$$という関係から、
$${H_2(S)=\displaystyle \frac {H_2(S^2)}{2}}$$

平均符号長

$${L(n)}$$の$${\displaystyle \lim_{ n \to \infty }L^{(n)} }$$を考える。