レッスン
理論 — 定常マルコフ連鎖エクスプローラー
さらに1ステップ進めても何も変化しないとき、分布は定常であると言います：πP = π。これは遷移行列の不動点です — チェーンは状態間を移動し続けますが、その割合は変化しなくなります。
各記号の意味
P- 遷移行列。第i行・第j列の成分は、状態iから状態jへ移動する確率であり、各行の和は必ず1になります — 上のグリッドが自動でチェックしてくれます。
p(0)- 初期分布：チェーンの始点。デフォルトの
(1, 0, 0)は、確実に状態1から始まることを意味します。 p(k)- kステップ後の分布。1ステップごとに
Pを掛けることで得られます。 π- 定常分布 —
πP = πを満たす分布。 k- 実行するステップ数（上で設定）。軌跡テーブルには、
p(0)からp(k)までのすべての分布が表示されます。
公式の導き方
- 定常性の条件を書き下します：1ステップ後も分布は変化しないため、
πP = πとなります。 - 変形すると
π(P − I) = 0となります — これは状態ごとに1つの式を持つ連立一次方程式です。解の定数倍もすべて解となるため、これ単体では解が無限に存在します。 - 確率分布としての条件
Σπ = 1を加えることで、解が一意に決まります。デフォルトの行列では正確に8/13, 3/13, 2/13となり — 上記で報告されている0.615385, 0.230769, 0.153846に相当します。
表示の読み方
3つのパネルから構成されています。p(k)は設定したkステップ後にチェーンが実際に存在する分布、πは到達を目指す分布（反復回数や収束したかどうかを含む）であり、定常性への距離はそれら2つの間の隔たりを測定します — デフォルトのk = 8では0.08893であり、注釈でチェーンがまだ完全に混合していないと書かれているのはこのためです。下の軌跡テーブルには、(1, 0, 0)から始まる各ステップが示されています。
- 前提
- 有限の状態で構成され、遷移確率が時間とともに変化しないことを前提としています。各行の和が1になるのは単なる表示上のルールではなく、毎ステップでチェーンが必ずどこかへ移動するという事実を表しています。
- 成り立たない場合
- 上記の
πが推定値とラベル付けされているのには理由があります：チェーンのステップを繰り返し実行し（デフォルトの行列では83回の反復）、連続する分布の変動が収まったところで計算を停止して得られるためです。これは数値的な判断であり、厳密な証明ではありません。ここでの厳密な解は有理数の集合8/13, 3/13, 2/13であり、表示されている小数はこちらを小数点以下第6位で丸めたものです。
練習
自分で確かめる
まず答えを予想し、それから上のコントロールで確かめてください。予想を決めてから答えを開くこと。それが練習になる条件です。
-
初期状態では、鎖は確率1で状態1から始まります（
p(0) = (1, 0, 0)）。これを(0, 0, 1)に変えて、状態3から始めてみてください。どの表示が動き、どれが動かないか予想してみましょう。答えを表示
動くのはp(k)と距離、動かないのはπと反復回数です。状態1からは8ステップで0.659852, 0.218714, 0.121436に達し、距離は0.08893。状態3からは0.522304, 0.255274, 0.222421に達し、距離は0.18616と遠くなります。状態3が最もまれな行き先だからです。どちらの場合もπは同じ83回の反復のあと0.615385, 0.230769, 0.153846を示します。出発点が決めるのは鎖がどこまで進んだかであって、どこへ向かうかではありません。πP = πに出てくるのは行列だけです。 -
(1, 0, 0)に戻し、今度はステップ数を上げてください。定常状態までの距離が0と表示されるのは何ステップからで、そのとき鎖は到達しているのでしょうか。答えを表示
k = 80で0と出ますが、到達してはいません。k = 40の時点で距離はすでに0.000024。パネルが表示する小数6桁のほうが、差より先に尽きているだけです。この鎖はπに幾何級数的に近づき、有限回のステップで到達することはありません。つまり0は表示の丸めであり、π自体が推定値と明記されているのと同じ理由です。距離が0.08893で「まだ混ざっていない」と注記されるk = 8と比べてみてください。
全プロセスの詳細解説
-
状態1から始まる3状態連鎖の8ステップ 5 ステップ
完全に状態1から開始し、8ステップ実行された3状態の連鎖。これがどこに向かっているのか、そして到達するまでにあとどれほど離れているかを求めよ。
-
1ステップの推移はベクトルと行列の積である。次に状態 j にいる確率は、現在状態 i にいる確率と i → j へ移動する確率の積を、すべての i について足し合わせた和となる。
-
それを8ステップ進めると、パネルに表示される分布が得られる。この連鎖が確実に状態1から開始したことを考慮しても、状態1が依然として確率の3分の2を占めているのは大きな割合である。
-
行き着く先は定常分布、すなわち1ステップの推移で変化しない分布である。確率の総和が1になるという条件のもとで πP = π を解くと、小数ではなく、8分の1や13分の1といった正確な分数が得られる。
-
この2つを比較するとパネルに表示される距離が得られるが、その値は小さくはない。8ステップを経ても、この連鎖は全体としてまだ約0.089離れている。
-
その隔たりは P の2番目に大きい固有値によって支配され、幾何級数的に縮小する。幾何級数的な減少とは、定められたステップ数ごとに半減し、有限回のステップでは決してゼロに達しないことを意味する。
解答
ツールは8ステップ後に0.65985, 0.218714, 0.121436と表示し、定常状態からは依然として0.08893離れている。定常分布は正確に (8/13, 3/13, 2/13) であり、ここで心に留めておくべき事実は、それがどこから開始したかに依存しないということである。これら全く同じ3つの分数があらゆる初期分布からの極限となり、それゆえ特定の試行結果ではなく遷移行列固有の性質となるのである。この独立性こそが定常分布を有用なものにしている。PageRank、MCMCサンプリング、待ち行列の占有状況のいずれも、長期的な結果が遷移規則のみの性質であるという点に依拠している。そこに到達するまでにかかる時間だけが、初期状態に依存するのである。
-
参考文献 (1)
- The stationary distribution put to work on the whole web, damping factor and all: S. Brin & L. Page, “The anatomy of a large-scale hypertextual Web search engine.” Computer Networks and ISDN Systems 30, 107–117, 1998.