不変分布を計算してみるリンクリンク不変分布とは?マルコフ連鎖とは今の状態にのみ依存して次の状態が確率的に決まるようなモデルで、次の状態へ移行する確率を遷移確率行列で表しました。遷移確率行列をn乗すると、それはn時間ステップ先の遷移確率行列になります。nがある程度大きくなると、そこからいくらnを大きくしても遷移確率行列は変わらなくなる場合がある、つまり収束する場合があることを前回の記事で見ました。【マルコフ連鎖】翌日配送が翌々日配送になると在庫は何台必要か?次のように、P6で既に収束していることが分かります。P6の行列を見ると、tの状態に関わらずt+6の各状態へ遷移する確率はすべて同じになっていることが分かります。0.64]のように省略して書いても情報量としては同じです。このベクトルは不変分布と呼ばれ、Πで表します。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なので4ですね。その次に短いルートはいくつでしょうか?そのルートは状態0⇒状態1⇒状態2⇒状態0⇒状態2⇒状態1⇒状態0なので6ですね。状態0から状態1に遷移した場合、再び状態0に戻ってくる距離は2と4と6の3通りあります。すべて最短距離である2の倍数になっています。このような時、状態0の周期は2であるといいます。状態0は周期的(periodic)であるといいます。最短距離は2以上でないといけません。ここで、最初の状態遷移図をもう一度見てみましょう。状態0から状態2に遷移した場合、戻ってこれる最短距離は状態0⇒状態2⇒状態0の2ですね。次に短い距離は状態0⇒状態2⇒状態2⇒状態0の3になりますね。この場合3は2の倍数でないため状態0は周期的とはいえません。この場合、状態0は非周期的(aperiodic)といいます。エルゴ―ド的=不変分布を持ついずれの状態の組み合わせも連結されていて、いずれの状態も再帰的で非周期的である時、そのマルコフ連鎖はエルゴ―ド的(ergodic)といいます。ここで、もう一度最初の状態遷移図を見て、エルゴ―ド的かどうかチェックしてみましょう。連結:すべての状態から他のすべての状態に到達可能(矢印がつながっている)なため、連結の条件を満たしています。再帰的:ある状態から遷移して、そのまま戻ってこれないという状態は存在しないため、すべての状態は再帰的です。非周期的:状態1と状態2は自分に直接戻ってくるルートがあります。そのためすべての状態の周期は2にはならずに1になります。そのためすべての状態は非周期的です。以上、3つの条件をすべて満たすため、このマルコフ連鎖はエルゴ―ド的といえます。エルゴ―ド的であるマルコフ連鎖は不変分布を持つことが知られています。そのため、前回の記事で見たように、このマルコフ連鎖の遷移確率行列のn乗はnを大きくすると不変分布に収束したのです。前回のマルコフ連鎖は遷移確率行列を6乗しただけで収束しましたが(n=6)、もっと遥かにnを大きくしないと収束しないマルコフ連鎖はたくさんあります。遷移確率行列のn乗を計算するのが大変ですね。そんな時に簡単に不変分布を計算する方法があります。ΠP=ΠここでΠは円周率ではなく、先に説明したように不変分布のことで、状態が3つなら3つの成分を持つベクトルです。不変分布とは遷移確率行列Pのn乗でnを大きくした時に収束する値ですから、もう1回Pを掛けても変わらないはずです。この公式はそのことを表現しています。不変分布を計算してみるそれでは、この公式を使って前回のマルコフ連鎖の不変分布を求めてみましょう。Π3]とすると、次式が成り立ちます。後は、1~3の連立方程式を解くだけです。この連立方程式は変数が3つで、式も3つありますので一意に解が求まりそうですが、1を3に代入すると、2と3は同じ式になってしまいます。変数が3つで式は2つしかないので、一意に解が決まりません。Π1+Π2+Π3=1は常に成り立ちますので、この式を含めると解は一意に決まります。その解はΠ1=0.04Π2=0.32Π3=0.64となり、遷移確率行列Pを6乗した成分と同じになります。このようにわざわざ遷移確率行列Pを何度も掛け算しなくても、連立一次方程式で簡単に不変分布が計算できるわけです。遺伝的アルゴリズムをExcelに実装して最小値問題を解いてみた。今回はいよいよニューラルネットワークによる機械学習の講座です。...ポアソン分布のパラメータλをExcelソルバーを使って最尤法で求めてみた。...【マルコフ連鎖と遷移確率行列】5年後に太ってしまう確率は何%?ある病院では毎年行っている健康診断で肥満度の統計をとっています。【区間推定の使い方】タイヤの摩耗を具体例にわかりやすく解説します。TOP28【作業分析6】MMCモデル|最適なトラックドック数をSimpyでシミュレーション【作業分析5】トラックの待機台数の多さを人の表情でアニメーション(2)カンボジアの物流でお困りのことがあればお気軽にご相談下さい。学生時代にアジアの雑踏にハマる。誰もが羨むメーカーを退職し「旅するように働く」ことを目指し物流業界に転職。理工学と経営学のダブル修士。2023年1月からカンボジアのオートレスビーチ在住。