マルコフ連鎖が不変分布に収束するための条件を図でわかりやすく解説
不変分布とは？
マルコフ連鎖とは今の状態にのみ依存して次の状態が確率的に決まるようなモデルで、次の状態へ移行する確率を遷移確率行列で表しました。
また遷移確率行列をｎ乗すると、それはｎ時間ステップ先の遷移確率行列になります。
そしてｎがある程度大きくなると、そこからいくらｎを大きくしても遷移確率行列は変わらなくなる場合がある、つまり収束する場合があることを前回の記事で見ました。
【マルコフ連鎖】翌日配送が翌々日配送になると在庫は何台必要か？
次のように、P６で既に収束していることが分かります。
またP６の行列を見ると、ｔの状態に関わらずｔ＋６の各状態へ遷移する確率はすべて同じになっていることが分かります。
ですから、このP６は
[0.04 0.32 0.64]
のように省略して書いても情報量としては同じです。
このベクトルは不変分布と呼ばれ、Πで表します。
Π＝[0.04 0.32 0.64]
この例では状態が３つあるため、Πは３つのベクトル成分を持ちます。
前回の例で見た遷移確率行列は６乗するだけで不変分布に辿り着きましたが、すべての遷移確率行列が不変分布に辿り着けるとは限りません。
つまり収束するとは限らないのです。
この不変分布に辿り着ける遷移確率行列の条件、またはマルコフ連鎖の条件は教科書やウェブサイト上にいろいろと紹介されていますが、なかなか分かりにくいと思います。
本記事では図を使いながらできるだけ分かり易く解説してみます。
状態遷移図を描く
前回の遷移確率行列は次のようでした。
状態は０、１、２の３つで、この遷移確率行列は１時間ステップ後に各状態から各状態へ遷移する確率を表しているので、次のように図示することができます。
これを状態遷移図といいます。
ある状態からある状態へ遷移する確率を書き入れただけなので簡単ですね。
但し、ゼロの確率は書き入れません。
到達可能とは？
ある状態から別の状態へ遷移する確率が０でない時、つまり矢印でつながっている時、到達可能（reachable）といいます。
例えば、状態０から状態２へは矢印でつながっているので到達可能です。
状態０から状態１へは１本の矢印ではつながっていませんが、状態２を経由する２本の矢印でつながっています。
ですので、状態０から状態１も到達可能です。
連結とは？
状態iから状態jへ到達可能で、状態jから状態iへも到達可能な時、状態iと状態jは連結（communicate）しているといいます。
上の図だと、３つの各状態からはすべて別の状態へ遷移可能ですので、３つの状態はすべて連結しています。
しかし、もし状態遷移図が下のようになる場合には、状態１と状態２は連結しているが状態０は連結していません。
再帰的とは？
次に状態遷移図が下図のようになっている場合を想定してみます。
この場合、状態１や状態２から状態０へは到達可能です。
しかし、状態０から状態１や状態２へは到達できません。
なぜなら、一旦、状態０に行ったらずっと状態０に居続けることになるからです。（状態０から状態０へ遷移する確率が１だから）
言い方を変えると、状態１や状態２からは戻ってこれないルートがあります。
このような場合、状態１や状態２は一時的（transient）といいます。
そして一時的でない状態を再帰的（recurrent）といいます。
つまり一時的と再帰的は互いに相反関係にあります。
最初の状態遷移図では、一旦違う状態に移っても戻ってこれないルートは存在しないため、すべての状態は再帰的です。
非周期的とは？
次に状態遷移図が次のような場合を想定してみましょう。
この時、状態０から状態１に遷移して、また状態０に戻ってくる最短距離は２ですね。
では次に短い距離はいくつでしょう？
そのルートは状態０⇒状態１⇒状態２⇒状態１⇒状態０なので４ですね。
ではその次に短いルートはいくつでしょうか？
そのルートは状態０⇒状態１⇒状態２⇒状態０⇒状態２⇒状態１⇒状態０なので６ですね。
つまり、状態０から状態１に遷移した場合、再び状態０に戻ってくる距離は２と４と６の３通りあります。
そして、すべて最短距離である２の倍数になっています。
このような時、状態０の周期は２であるといいます。
そして状態０は周期的（periodic）であるといいます。
但し、最短距離は２以上でないといけません。
ここで、最初の状態遷移図をもう一度見てみましょう。
状態０から状態２に遷移した場合、戻ってこれる最短距離は状態０⇒状態２⇒状態０の２ですね。
次に短い距離は状態０⇒状態２⇒状態２⇒状態０の３になりますね。
ですので、この場合３は２の倍数でないため状態０は周期的とはいえません。
この場合、状態０は非周期的（aperiodic）といいます。
エルゴ―ド的＝不変分布を持つ
いずれの状態の組み合わせも連結されていて、いずれの状態も再帰的で非周期的である時、そのマルコフ連鎖はエルゴ―ド的（ergodic）といいます。
ここで、もう一度最初の状態遷移図を見て、エルゴ―ド的かどうかチェックしてみましょう。
連結：すべての状態から他のすべての状態に到達可能（矢印がつながっている）なため、連結の条件を満たしています。
再帰的：ある状態から遷移して、そのまま戻ってこれないという状態は存在しないため、すべての状態は再帰的です。
非周期的：状態１と状態２は自分に直接戻ってくるルートがあります。そのためすべての状態の周期は２にはならずに１になります。そのためすべての状態は非周期的です。
以上、３つの条件をすべて満たすため、このマルコフ連鎖はエルゴ―ド的といえます。
そしてエルゴ―ド的であるマルコフ連鎖は不変分布を持つことが知られています。
そのため、前回の記事で見たように、このマルコフ連鎖の遷移確率行列のｎ乗はｎを大きくすると不変分布に収束したのです。
不変分布を簡単に求める公式～ΠＰ＝Π
前回のマルコフ連鎖は遷移確率行列を６乗しただけで収束しましたが（ｎ＝６）、もっと遥かにｎを大きくしないと収束しないマルコフ連鎖はたくさんあります。
でもそうだと、遷移確率行列のｎ乗を計算するのが大変ですね。
そんな時に簡単に不変分布を計算する方法があります。
その公式がこれです。
ΠＰ＝Π
ここでΠは円周率ではなく、先に説明したように不変分布のことで、状態が３つなら３つの成分を持つベクトルです。
不変分布とは遷移確率行列Ｐのｎ乗でｎを大きくした時に収束する値ですから、もう１回Ｐを掛けても変わらないはずです。
この公式はそのことを表現しています。
不変分布を計算してみる
それでは、この公式を使って前回のマルコフ連鎖の不変分布を求めてみましょう。
Π＝［Π１ Π２ Π３］
とすると、次式が成り立ちます。
後は、①～③の連立方程式を解くだけです。
この連立方程式は変数が３つで、式も３つありますので一意に解が求まりそうですが、①を③に代入すると、②と③は同じ式になってしまいます。
つまり、変数が３つで式は２つしかないので、一意に解が決まりません。
しかし、
Π１＋Π２＋Π３＝１
は常に成り立ちますので、この式を含めると解は一意に決まります。
そしてその解は
Π１＝０.０４
Π２＝０.３２
Π３＝０.６４
となり、遷移確率行列Pを６乗した成分と同じになります。
このようにわざわざ遷移確率行列Pを何度も掛け算しなくても、連立一次方程式で簡単に不変分布が計算できるわけです。