マルコフ連鎖が不変分布に収束するための条件を図でわかりやすく解説

Photo by Trung Pham Quoc on Unsplash

【沸騰アジア!】

親日国カンボジアであなたの会社の商品を販売してみませんか?

食品/飲料ヘルスケアコスメ商流と物流を管理人がサポートします。

Naga World in Phnom Penh (2022)

不変分布とは?

マルコフ連鎖とは今の状態にのみ依存して次の状態が確率的に決まるようなモデルで、次の状態へ移行する確率を遷移確率行列で表しました。

また遷移確率行列をn乗すると、それはn時間ステップ先の遷移確率行列になります。

そしてnがある程度大きくなると、そこからいくらnを大きくしても遷移確率行列は変わらなくなる場合がある、つまり収束する場合があることを前回の記事で見ました。

【マルコフ連鎖】翌日配送が翌々日配送になると在庫は何台必要か?

 

次のように、Pで既に収束していることが分かります。

 

またPの行列を見ると、tの状態に関わらずt+6の各状態へ遷移する確率はすべて同じになっていることが分かります。

 

ですから、このP

[0.04  0.32  0.64]

のように省略して書いても情報量としては同じです。

このベクトルは不変分布と呼ばれ、Πで表します。

Π=[0.04  0.32  0.64]

この例では状態が3つあるため、Πは3つのベクトル成分を持ちます。

 

前回の例で見た遷移確率行列は6乗するだけで不変分布に辿り着きましたが、すべての遷移確率行列が不変分布に辿り着けるとは限りません。

つまり収束するとは限らないのです。

この不変分布に辿り着ける遷移確率行列の条件、またはマルコフ連鎖の条件は教科書やウェブサイト上にいろいろと紹介されていますが、なかなか分かりにくいと思います。

本記事では図を使いながらできるだけ分かり易く解説してみます。

 

状態遷移図を描く

前回の遷移確率行列は次のようでした。

 

状態は0、1、2の3つで、この遷移確率行列は1時間ステップ後に各状態から各状態へ遷移する確率を表しているので、次のように図示することができます。

 

これを状態遷移図といいます。

ある状態からある状態へ遷移する確率を書き入れただけなので簡単ですね。

但し、ゼロの確率は書き入れません。

 

到達可能とは?

ある状態から別の状態へ遷移する確率が0でない時、つまり矢印でつながっている時到達可能(reachableといいます。

例えば、状態0から状態2へは矢印でつながっているので到達可能です。

状態0から状態1へは1本の矢印ではつながっていませんが、状態2を経由する2本の矢印でつながっています。

ですので、状態0から状態1も到達可能です。

 

連結とは?

状態iから状態jへ到達可能で、状態jから状態iへも到達可能な時、状態iと状態jは連結(communicateしているといいます。

上の図だと、3つの各状態からはすべて別の状態へ遷移可能ですので、3つの状態はすべて連結しています。

しかし、もし状態遷移図が下のようになる場合には、状態1と状態2は連結しているが状態0は連結していません。

 

再帰的とは?

次に状態遷移図が下図のようになっている場合を想定してみます。

 

この場合、状態1や状態2から状態0へは到達可能です。

しかし、状態0から状態1や状態2へは到達できません

なぜなら、一旦、状態0に行ったらずっと状態0に居続けることになるからです。(状態0から状態0へ遷移する確率が1だから)

 

言い方を変えると、状態1や状態2からは戻ってこれないルートがあります。

このような場合、状態1や状態2は一時的(transientといいます。

そして一時的でない状態を再帰的(recurrentといいます。

つまり一時的と再帰的は互いに相反関係にあります。

最初の状態遷移図では、一旦違う状態に移っても戻ってこれないルートは存在しないため、すべての状態は再帰的です。

 

非周期的とは?

次に状態遷移図が次のような場合を想定してみましょう。

 

この時、状態0から状態1に遷移して、また状態0に戻ってくる最短距離は2ですね。

では次に短い距離はいくつでしょう?

そのルートは状態0⇒状態1⇒状態2⇒状態1⇒状態0なのでですね。

ではその次に短いルートはいくつでしょうか?

そのルートは状態0⇒状態1⇒状態2⇒状態0⇒状態2⇒状態1⇒状態0なのでですね。

つまり、状態0から状態1に遷移した場合、再び状態0に戻ってくる距離は2と4と6の3通りあります。

そして、すべて最短距離である2の倍数になっています。

このような時、状態0の周期は2であるといいます。

そして状態0は周期的(periodicであるといいます。

但し、最短距離は2以上でないといけません

 

ここで、最初の状態遷移図をもう一度見てみましょう。

 

状態0から状態2に遷移した場合、戻ってこれる最短距離は状態0⇒状態2⇒状態0のですね。

次に短い距離は状態0⇒状態2⇒状態2⇒状態0のになりますね。

ですので、この場合3は2の倍数でないため状態0は周期的とはいえません。

この場合、状態0は非周期的(aperiodicといいます。

 

エルゴ―ド的=不変分布を持つ

いずれの状態の組み合わせも連結されていて、いずれの状態も再帰的非周期的である時、そのマルコフ連鎖はエルゴ―ド的(ergodicといいます。

ここで、もう一度最初の状態遷移図を見て、エルゴ―ド的かどうかチェックしてみましょう。

 

連結:すべての状態から他のすべての状態に到達可能(矢印がつながっている)なため、連結の条件を満たしています。

再帰的:ある状態から遷移して、そのまま戻ってこれないという状態は存在しないため、すべての状態は再帰的です。

非周期的:状態1と状態2は自分に直接戻ってくるルートがあります。そのためすべての状態の周期は2にはならずに1になります。そのためすべての状態は非周期的です。

 

以上、3つの条件をすべて満たすため、このマルコフ連鎖はエルゴ―ド的といえます。

そしてエルゴ―ド的であるマルコフ連鎖は不変分布を持つことが知られています。

そのため、前回の記事で見たように、このマルコフ連鎖の遷移確率行列のn乗はnを大きくすると不変分布に収束したのです。

 

不変分布を簡単に求める公式~ΠP=Π

前回のマルコフ連鎖は遷移確率行列を6乗しただけで収束しましたが(n=6)、もっと遥かにnを大きくしないと収束しないマルコフ連鎖はたくさんあります。

でもそうだと、遷移確率行列のn乗を計算するのが大変ですね。

そんな時に簡単に不変分布を計算する方法があります。

その公式がこれです。

 

ΠP=Π

 

ここでΠは円周率ではなく、先に説明したように不変分布のことで、状態が3つなら3つの成分を持つベクトルです。

不変分布とは遷移確率行列Pのn乗でnを大きくした時に収束する値ですから、もう1回Pを掛けても変わらないはずです。

この公式はそのことを表現しています。

 

不変分布を計算してみる

それでは、この公式を使って前回のマルコフ連鎖の不変分布を求めてみましょう。

Π=[Π Π Π

とすると、次式が成り立ちます。

 

後は、①~③の連立方程式を解くだけです。

この連立方程式は変数が3つで、式も3つありますので一意に解が求まりそうですが、①を③に代入すると、②と③は同じ式になってしまいます。

つまり、変数が3つで式は2つしかないので、一意に解が決まりません。

しかし、

Π+Π+Π=1

は常に成り立ちますので、この式を含めると解は一意に決まります。

そしてその解は

Π=0.04

Π=0.32

Π=0.64

となり、遷移確率行列Pを6乗した成分と同じになります。

このようにわざわざ遷移確率行列Pを何度も掛け算しなくても、連立一次方程式で簡単に不変分布が計算できるわけです。