二状態マルコフ連鎖(続)

二状態マルコフ連鎖で表される情報源は、十分長いメッセージをとると、各状態での滞在時間の割合がある定常分布に収束します。すなわち、

とおくと、xの割合で状態αに、1-xの割合で状態βに滞在することになる。前回はこの結果をもとに、状態αにある確率P(α)をxで定義しました。

さて、非常に長い時間tをとって実際の遷移の履歴を観測したとします。このときの観測結果は例えば以下のようになるでしょう:

この中に含まれるpの個数をN(p)とします。前の結果より状態αにいる割合はxなので、pの個数とq'の個数を列の長さtで割ったものは、xに(ほぼ等しく)ならないといけない。(正確には、ほぼ等しくなることが確実。)よってここからq'の個数N(q')が

N(q') = xt - N(p)

と書けるでしょう。同様にN(q)とN(p')の和は(ほぼ)(1-x)tに等しいはず。

ここでさらに話をシンプルにするために、最初と最後の遷移がpだったとします。(そうでない場合もまったく同様の議論ができます。)すると別の状態への遷移を表すp'とq'は同じ数だけあるはずです。よってN(p')=N(q')がいえる。するとここから

N(q) = (1-x)t - (xt - N(p))

が出てきます。つまりすべてのNがN(p)で表されるわけです。

次にN(p)が動ける範囲を考えます。条件を列挙すると以下のとおり:

これを整理すると

となります。

ここまでの議論で各遷移の出てくる回数をN(p)の関数として表せたわけですが、さらにある固定されたN(p)に対応する異なる遷移の系列がどれほどあるか考えてみます。pとqはそれぞれq'とp'の直後にしか起こり得ません。ただしそれさえ満たせば複数回連続で起きてもいい。するとまずp'とq'をこの順で交互にxt-N(p)個ずつ並べ、その間にpとqを、重複を許して並べる順列の個数を求めればよいでしょう。図式にすると:

つまり一定数の箱の中に、一定数のボールを割り振るパターンの数に帰着されます。これは箱の数マイナス１だけの区別できない「|」と、これまた区別できないボールの順列の個数に等しい。箱の個数とボールの個数はすべてN(p)で表せているので、異なる列の総数は以下のように計算できます。まずp, qの並べ方の総数はそれぞれ

となります。ここでx'=1-xです。異なる系列の総数はこれらの積になるのですが、さらにスターリングの公式を用いて指数関数のかたちに書き直せば、変動の比較的緩やかな部分を除いて、

となります。ここでN(p)/tを新たにuと書きました。さらに見通しのよいかたちに変形すれば、

となります。つまり指数関数の肩の部分は、状態がわかっているときの遷移確率に対応する、実測された条件つきエントロピーになっているのです。

条件つきエントロピーの部分は、簡単な極値問題を解けば、u=x^2で最大値をとることがわかります。(uのとりうる範囲に対する条件も満たしています。)このuの特別な値は、図式化すると以下のようになります。

つまりαとβの分布と同じ構造を、pとp'もしくはqとq'にもちこむことに対応するのです。

このとき条件つきエントロピーの値は定常分布のエントロピーに一致します。いまtは非常に大きいので、このuの値のところで列のパターン数は鋭いピークをとり、全パターンのほぼすべてを占めることになります。定常分布のエントロピーをH(x)とすれば、このピークに対応するメッセージの個数はexp[tH(x)]のかたちで指数関数的に増えていきます。つまり各メッセージをpの個数で分類したとき、x^2の割合で含むものが全体のほとんどを占め、その増大の速さを決めているのが定常分布のエントロピーなのです。

次に確率もこみで考えてみます。遷移pの割合がuであるような系列が実現する確率は、前の結果もふまえて、

となることがわかります。相対エントロピーは分布が完全に一致するときに限り最小値ゼロをとりますが、実際u=xpとすると最小値が達成されます。逆にそうでないようなメッセージはexp(-Dt)のように指数関数的に減少し、その速さは条件つき相対エントロピーDで与えられることがわかります。

このu=xpという解は直観的にも理解しやすいと思います。それぞれの状態にいる確率がx, x'であり、そこからの実測された遷移確率が、遷移確率行列と一致するようなuが、最も典型的だ、という結果だからです。このようなメッセージの個数と確率はそれぞれ、

となります。ここでHは条件つきエントロピーです。つまりメッセージが十分長ければ、そこにはほぼ確実に遷移pがxpの割合だけ含まれている。そのような特別なメッセージのみが、すべて等確率で出現するとみなしても差し支えないということになるわけです。

また確率論的に考えれば、確率空間において、u≒xpの列全体の作る部分集合が確率(ほぼ)１の事象を構成し、その部分集合に対応するbit-numberの単位時間あたりの生成速度がHに等しい、とも解釈できます:

以上の結果は、ベルヌーイ試行におけるエントロピーと相対エントロピーが、それぞれ条件つきエントロピーと条件つき相対エントロピーに変わっただけです。さらにこの結果はベルヌーイ試行の結果を特殊な場合として含んでいます。(遷移確率行列の行が一致している場合。)

次回は情報源の内部状態と記号の生成を関連付けて、その符号化の能率という観点を調べていきます。