更新:2025/03/27

【入門】マルコフ連鎖とマルコフ性・遷移行列・定常分布について

私たちの身の回りには、「現在の状況に応じて次の出来事が決まる」ような現象がたくさんあります。たとえば、明日の天気は今日の天気によってある程度予測できますし、ある商品を買った人が次に何を買うかも、今の選択に影響を受けることがあります。このような「現在の状態に基づいて次の状態が決まる仕組み」を数学的に表現するのが、マルコフ連鎖(Markov Chain)という考え方です。

はるか
はるか
次がどうなるか、今だけ見ればいい。過去は関係ない。

ふゅか
ふゅか
それがマルコフ連鎖の面白いところよね!

1. 前提知識

1.1. 確率論の基礎

1.1.1. (1) 確率とは

確率 \(P(A)\) は「ある事象 \(A\) が起こる ‘起こりやすさ’」を 0 ~ 1 の実数で表したものです。例えばサイコロを振って「1の目が出る事象」を \(A\) とすれば、理想的なサイコロなら

\[ P(A) = \frac{1}{6} \]

となります。

1.1.2. (2) 確率変数と分布

確率変数とは、偶然に左右される値(変数)を数値で表したものです。例として、サイコロの出目を \(X\) とすると、

\[ X \in \{1, 2, 3, 4, 5, 6\} \]

のように整数値を取ります。各値を取る確率の集合を分布(probability distribution)と呼びます。

1.1.3. (3) 条件付き確率

確率論で重要な概念の一つが条件付き確率です。事象 \(B\) が起きたという情報が与えられたときに、事象 \(A\) が起きる確率を

\[ P(A \mid B) = \frac{P(A \cap B)}{P(B)} \]

と書きます。ここで \(P(B) \neq 0\) が前提です。マルコフ連鎖では「現在の状態がわかっているときに、次がどうなるか」という確率を多用するので、条件付き確率の概念が根幹を支えています。

1.2. 行列の基礎

マルコフ連鎖では、遷移確率行列と呼ばれる行列を使って「状態間の移り変わり」を表します。行列は二次元の数の配置であり、例えば \(2 \times 2\) の行列ならば

\[ \begin{pmatrix} a & b \\ c & d \end{pmatrix} \]

という形を取ります。

1.2.1. (1) 行列の積

行列の積は、対応する行と列の要素を掛け合わせて足し合わせることで求まります。

$$ \begin{pmatrix} a & b \\ c & d \end{pmatrix} \begin{pmatrix} e & f \\ g & h \end{pmatrix}=\begin{pmatrix} ae + bg & af + bh \\ ce + dg & cf + dh \end{pmatrix}$$

1.2.2. (2) ベクトルとの積

マルコフ連鎖で頻繁に出てくるのは「行列とベクトルの積」です。例えば行ベクトル \(\pi = (x, y)\) と上記の \(2 \times 2\) 行列の積は

\[ \pi \begin{pmatrix} a & b \\ c & d \end{pmatrix} = (x, y) \begin{pmatrix} a & b \\ c & d \end{pmatrix} = (xa + yc,\; xb + yd). \]

はるか
はるか
分布の更新に使う。行列とベクトルの積。

ふゅか
ふゅか
「今の状態から次の状態へ」ってことを表すんだね!

2. マルコフ連鎖

2.1. マルコフ性 (Markov property)

マルコフ連鎖の重要な性質が「マルコフ性」です。これは、過去の情報がすべて分かっていても、結局「現在の状態」さえ分かれば次の状態の分布が決定されるという性質を示しています。式で書くと、

\[ P\bigl(X_{n+1} = x_{n+1} \mid X_n = x_n, X_{n-1} = x_{n-1}, \dots, X_1 = x_1\bigr) = P\bigl(X_{n+1} = x_{n+1} \mid X_n = x_n\bigr). \]

ここで \(X_n\) は「時刻 \(n\) における状態」を表す確率変数です。

簡単な例でいうと、「明日の天気は今日が晴れである」という情報だけで充分であり、“一昨日が雨だったかどうか” などの情報は考えなくていい、というイメージです。このように、マルコフ連鎖では現在の状態だけが鍵になります。

2.2. 状態空間

マルコフ連鎖を扱う上で、状態が取り得る値の集合を状態空間(state space) と呼びます。たとえば

  • サイコロの目:\(\{1, 2, 3, 4, 5, 6\}\)
  • 天気:\(\{\text{晴れ}, \text{曇り}, \text{雨}\}\)

のように有限個であれば「有限マルコフ連鎖」となり、状態空間が無限や連続だと「連続マルコフ連鎖」などと呼ばれます。本記事では理解しやすいように、有限マルコフ連鎖を中心に解説します。

3. 遷移確率と遷移確率行列

3.1. 1ステップ遷移確率

離散的な時刻 \(n\) に着目し、状態空間を \(S = \{1, 2, \ldots, N\}\) としましょう。時刻 \(n\) において「状態 \(i\)」にあるとき、次の時刻 \(n+1\) に「状態 \(j\)」へ移る確率を

\[ p(i, j) = P\bigl(X_{n+1} = j \mid X_n = i\bigr) \]

と書きます。たとえば \(i = 1\) から \(j = 3\) に移る確率が 0.2 というふうに、1つひとつ定義できます。

3.2. 遷移確率行列 \(Q\)

すべての遷移確率 \(p(i,j)\) をまとめた行列を遷移確率行列と呼び、普通は \(Q\) と書きます。つまり

\[ Q = \begin{pmatrix} p(1,1) & p(1,2) & \cdots & p(1,N) \\ p(2,1) & p(2,2) & \cdots & p(2,N) \\ \vdots & \vdots & \ddots & \vdots \\ p(N,1) & p(N,2) & \cdots & p(N,N) \end{pmatrix} \]

各行の総和は 1 になります。なぜなら、ある状態 \(i\) にいるとき、次の瞬間には必ず何らかの状態に移るので、

\[ \sum_{j=1}^N p(i,j) = 1 \]

簡単に言うと、条件付確率の行列です。

はるか
はるか
行の合計は必ず1。

ふゅか
ふゅか
次にどこかには必ず行くってことだから、全部足したら1になるのね!なるほど!

4. 状態確率ベクトル

4.1.  定義と意味

ある時刻 \(n\) において、\[ p_n(k) = P(X_n = k) \quad (k \in S) \] という状態kである確率を考えます。これをまとめたベクトルを

\[ \pi_n = (\,p_n(1),\,p_n(2),\,\dots,\,p_n(N)\,) \]

として、状態確率ベクトルと呼びます。

要するに「各状態 \(k\) にいる確率を並べたベクトル」です。

\(\pi_n\) は必ず成分の総和が 1 となり、各成分が 0 以上なので、確率ベクトルと呼ばれます。

4.2. \(\pi_{n+1} = \pi_n Q\)

マルコフ連鎖のポイントは「時間が進むごとに、この確率ベクトルが遷移確率行列 \(Q\) によって更新される」ことです。時刻nからn+1の遷移において、ある状態$i$から$k$に遷移すると考えると

$$p_{n+1}(k)=\sum_{i=1}^{N}p_n(i)p_n(k)$$

これを、行列とベクトルで書くと

\[ \pi_{n+1} = \pi_n \,Q \]

これを繰り返し適用すると、

\[ \pi_n = \pi_0 Q^n \]

が成立します。ここで \(\pi_0\) は初期分布と呼ばれる、時刻 0 の状態確率ベクトルです。

5. 定常分布 (Stationary Distribution)

マルコフ連鎖の中心的な概念のひとつが「定常分布」です。

定常分布とは、あるベクトル \(\pi\) があって、1回遷移させても変わらない、すなわち

\[ \pi = \pi \, Q \]

を満たすとき、その \(\pi\) を定常分布(stationary distribution)と呼びます。

5.1. 直感的イメージ

もし確率ベクトルが \(\pi\) であれば、次の時刻も\(\pi\)のままなので、「長期的に見てずっと変わらない安定した確率分布」というイメージになります。

6. 例:2状態連鎖

簡単な例として、状態空間を \(S = \{A, B\}\)(2状態)とし、遷移確率行列を

\[Q = \begin{pmatrix} p(A,A) & p(A,B) \\ p(B,A) & p(B,B) \end{pmatrix} \begin{pmatrix} 0.7 & 0.3 \\ 0.4 & 0.6 \end{pmatrix} \]

とします。ここで、行の合計が 1 になることを確認してください。この \(Q\) に対し「\(\pi = (\pi_A, \pi_B)\)」が定常分布となるには

\[ (\pi_A, \pi_B) \begin{pmatrix} 0.7 & 0.3 \\ 0.4 & 0.6 \end{pmatrix} = (\pi_A, \pi_B) \]

とならねばなりません。すなわち

\[ \begin{cases} \pi_A = 0.7\,\pi_A + 0.4\,\pi_B, \\ \pi_B = 0.3\,\pi_A + 0.6\,\pi_B, \end{cases} \quad \text{かつ} \quad \pi_A + \pi_B = 1. \]

これを解くと

\[ \pi_A = \frac{4}{7}, \quad \pi_B = \frac{3}{7} \]

となります。したがって \[ \pi = \left(\frac{4}{7},\;\frac{3}{7}\right) \]

PR