マルコフ連鎖 — 遷移行列と応用

マルコフ連鎖は、晴れと雨のような状態のあいだを、段階ごとに移っていくシステムを表すモデルです。重要なルールは、モデル化している対象に対してそれが妥当な仮定であるなら、次の段階は現在の状態だけに依存するということです。

その1ステップ先の確率をまとめたものが、遷移行列です。いま状態 $i$ にいて、次に状態 $j$ へ確率 $P_{ij}$ で移るなら、

$$P = (P_{ij})$$

と書きます。

有限マルコフ連鎖では、過程は許された次の状態のどれかに必ず移るので、$P$ の各行の和は $1$ になります。

マルコフ性とは何か

形式的には、次のように表します。

$$P(X_{n+1} = j \mid X_n = i, X_{n-1}, \ldots, X_0) = P(X_{n+1} = j \mid X_n = i)$$

これは、現在の状態 $X_n = i$ がわかっていれば、それより前の履歴はモデルの中で次の段階の確率を変えない、という意味です。

この条件は重要です。実際のシステムには記憶、傾向、遅れて現れる影響があることもあるので、「現在の状態だけで十分」という近似が妥当なときにだけ、マルコフ連鎖は適したモデルになります。

遷移行列の読み方

簡単な天気モデルに、次の2つの状態があるとします。

• 晴れ
• 雨

次の遷移行列を使います。

$$P = \begin{bmatrix} 0.8 & 0.2 \\ 0.4 & 0.6 \end{bmatrix}$$

各行を現在状態、各列を次の状態として読みます。

したがって、今日が晴れなら、モデルでは明日が晴れである確率は $0.8$、雨である確率は $0.2$ です。今日が雨なら、明日が晴れである確率は $0.4$、雨である確率は $0.6$ です。

計算例：2日間の天気

今日の分布が

$$\mathbf{v}_0 = \begin{bmatrix} 1 & 0 \end{bmatrix}$$

だとします。

これは、モデルが確率 $1$ で晴れから始まることを意味します。

明日の分布は

$$\mathbf{v}_1 = \mathbf{v}_0 P = \begin{bmatrix} 1 & 0 \end{bmatrix} \begin{bmatrix} 0.8 & 0.2 \\ 0.4 & 0.6 \end{bmatrix} = \begin{bmatrix} 0.8 & 0.2 \end{bmatrix}$$

となります。

つまり1ステップ後には、モデルは晴れの確率を $80\%$、雨の確率を $20\%$ と与えます。

さらにもう1ステップ進めると、

$$\mathbf{v}_2 = \mathbf{v}_1 P = \begin{bmatrix} 0.8 & 0.2 \end{bmatrix} \begin{bmatrix} 0.8 & 0.2 \\ 0.4 & 0.6 \end{bmatrix} = \begin{bmatrix} 0.72 & 0.28 \end{bmatrix}$$

となります。

このとき、晴れの確率は $0.72$、雨の確率は $0.28$ です。

大事なのは計算そのものだけではありません。行列によって確率分布全体を1ステップずつ更新できるので、繰り返し進む過程を扱うのにマルコフ連鎖は役立ちます。

マルコフ連鎖はどこで使われるか

マルコフ連鎖は、システムが段階的に変化し、その次に何が起こるかの確率を知りたいときに役立ちます。

よくある例としては、天気モデル、ボードゲームでの移動、待ち行列モデル、単純化したWeb上の移動などがあります。どの場合でも、状態の取り方が適切で、遷移確率が現実的であるときにだけ、このモデルは有効です。

よくあるマルコフ連鎖の間違い

ランダムな過程なら何でもマルコフだと考える

ランダムだからといって、自動的にマルコフ連鎖になるわけではありません。定義した状態に対して、次の段階の振る舞いが現在状態によって決まる必要があります。

行の意味を取り違える

行と列を混同しがちです。規約を一貫させる必要があります。このページでは、行が現在状態、列が次の状態です。

不正な確率を使う

各成分は $0$ から $1$ のあいだでなければならず、有限マルコフ連鎖の標準的な遷移行列では各行の和が $1$ でなければなりません。

モデルが1つの確定した未来を予測すると考える

マルコフ連鎖が与えるのは通常、確定ではなく確率です。ある状態がより起こりやすくても、次の状態として複数の可能性が残ることがあります。

長期的な振る舞いは連鎖によって異なる

マルコフ連鎖の中には、長い時間がたつと安定した分布に近づくものがあり、これは定常分布と呼ばれることが多いです。ただし、すべての連鎖でそうなるわけではなく、状態どうしの行き来のしかたや、移動パターンが周期的かどうかといった性質に依存します。

したがって、$P$ を繰り返し掛けることを長期的な振る舞いを調べる方法として考えるのはよいですが、条件を確かめずに収束を仮定してはいけません。

マルコフ連鎖がよいモデルになるとき

次のすべてがだいたい成り立つなら、マルコフ連鎖を使えます。

• 過程を、扱いやすい数の状態で記述できる。
• 時間が離散的なステップで進む、またはそのようにモデル化している。
• 次の段階の確率が、現在状態によって意味のある形で決まる。

これらの条件が成り立たない場合でも、粗い近似として使えることはありますが、そのことは明示しておくべきです。

自分で試してみよう

たとえば、需要が低・中・高の3状態モデルを作ってみましょう。各行の和が $1$ になるように確率を決め、初期分布を選び、$\mathbf{v}_{n+1} = \mathbf{v}_n P$ で次のステップを計算します。さらに進めたいなら、もう一度更新して、分布があるパターンに落ち着き始めるかを見てみましょう。