マルコフ連鎖シミュレーション

この実験について

マルコフ連鎖は状態間をランダムに移動しますが、各移動の確率は、そこに至るまでの経緯ではなく、現在の状態だけで決まります。明日の天気は今日の天気に、ウェブ閲覧者が次に見るページは現在のページに、分子の次の形は現在の形に依存します。連鎖がどのように始まっても、適切な性質を持つ連鎖は初期状態を忘れ、定常状態 π に落ち着きます。遷移確率を編集して連鎖を実行し、長期的な頻度と分布 pₙ が π に収束する様子を見てみましょう。

学習目標

マルコフ連鎖の遷移行列を書き、各行の合計が 1 になることを確認する
n ステップ後の分布を p₀Pⁿ として計算する
πP = π を解いて定常分布を求める
収束速度と P の第 2 位の固有値との関係を調べる
周期連鎖など、収束しない連鎖を見分ける

使い方

1Weatherチェーンで「実行」を押して、トークンの動きを観察しましょう。次に「1000ステップ」を押します。棒グラフは破線にどれくらい近づいていますか？
2初期状態を変えてみましょう。定常状態は変わりますか？上のグラフの序盤は変わりますか？
3定常状態を手計算で確認しましょう。πに行列を掛けて、πに戻ることを示してください。
4「ゆっくり混合」を選びます。上のグラフが落ち着くまでに何ステップ必要ですか？|λ₂|と表示値を比べてみましょう。
5「周期的なサイクル」を選びます。各状態にいる時間の割合は定まるのに、上のグラフが決して落ち着かないのはなぜですか？
6「すぐに忘れる」を選びます。分布が1ステップでπに達するのはなぜですか？

モデル

P_{ij} = Pr (X_{n + 1} = j ∣ X_{n} = i), j \sum P_{ij} = 1

遷移行列：各行は確率分布

p_{n} = p_{0} P^{n}

nステップ後の分布

π P = π, i \sum π_{i} = 1

定常分布：固有値1に対応するPの左固有ベクトル

∥ p_{n} - π ∥ \leq C ∣ λ_{2} ∣^{n}

2番目に大きい固有値が、連鎖が初期状態を忘れる速さを決める

\frac{1}{N} # {n \leq N : X_{n} = i} \to π_{i}

エルゴード定理：長期的に各状態にいる時間の割合

前提条件

3つの状態と時間に依存しない遷移確率です。各行は2つのスライダーで編集します。残りの確率がその状態にとどまる確率です。
サンプル経路はシード付き乱数生成器から得られるため、同じ実行番号なら常に同じ経路になります。「新しい実行」を選ぶとシードが変わります。
定常状態は連立一次方程式を厳密に解いて求めます。誤差を1 %以内にするために必要なステップ数は、ln 100 / (-ln |λ₂|) で推定されます。

授業で試してみましょう

Q1P = [[0.9, 0.1], [0.5, 0.5]] のとき、定常分布を求めなさい。
Q2P のすべての列の和も1であるとき、一様分布が定常分布であることを示しなさい。
Q3|λ₂| = 0.95 のマルコフ連鎖があります。初期状態を忘れるまでに、およそ何ステップ必要ですか？
Q4「周期的な循環連鎖」には定常分布があるのに、pₙ がその定常分布に収束しない理由を説明しなさい。
Q5Google の元祖 PageRank は、ランダムサーファーの定常分布です。なぜ、どのページにもジャンプする小さな確率を加えたのでしょうか？

よくある質問

ここで「記憶がない」とはどういう意味ですか？

未来は、現在の状態を通じてのみ過去に依存します。今日が雨だとわかっているなら、先週晴れていたと知っていても、明日のことについてそれ以上の情報は得られません。

すべての連鎖に定常状態がありますか？

有限状態のマルコフ連鎖には、少なくとも1つの定常分布があります。すべての状態から他のすべての状態へ到達できる場合、その分布は一意です。さらに連鎖が周期的でなければ、どの状態から始めても pₙ はその分布に収束します。

マルコフ連鎖はどこで使われていますか？

待ち行列モデルや信頼性モデル、遺伝学、音声認識、テキスト予測、金融のほか、サンプリングしたい分布を定常分布にもつ連鎖を構成するマルコフ連鎖モンテカルロ法で使われています。