\( \def\vector#1{\boldsymbol{#1}} \)

マルコフ連鎖

Takami Torao
  • このエントリーをはてなブックマークに追加

定義と性質

時刻やステップの推移で状態空間 \(\{1, 2, \ldots, k\}\) のいずれかの値を持つ確率変数について考える。ある時点 \(t\in(0, 1, \ldots)\) での確率変数を \(x^{(t)}\) とする。

確率過程 \((x^{(0)}, x^{(1)}, \cdots)\) において、ある確率変数 \(x^{(t+1)}\) が直前の確率変数 \(x^{(t)}\) のみに依存するとき、確率過程はマルコフ連鎖 (Markov chain)である。\[ \begin{equation} P(x^{(t+1)}| x^{(0)}, x^{(1)}, \ldots, x^{(t)}) = P(x^{(t+1)}|x^{(t)}) \label{markov} \end{equation} \]

マルコフ連鎖は \(t+1\) 時点での条件付確率分布が \(t\) 時点よりも前の履歴には依存しない確率過程である。この性質はマルコフ性 (Markov property) という。

推移行列

式 (\(\ref{markov}\)) の条件付確率より、時点 \(t\) から \(t+1\) への推移で状態空間の \(i\) から \(j\) へ移動する推移確率を \(P(x^{(t+1)}=j|x^{(t)}=i) = p(i,j)\) とするとき、推移確率の \(k\times k\) 行列を推移行列 (transition matrix) と呼ぶ。\[ \vector{T} = \left( \begin{array}{cccc} p(1,1) & p(1,2) & \cdots & p(1,k) \\ p(2,1) & p(2,2) & \cdots & p(2,k) \\ \vdots & \vdots & \ddots & \vdots \\ p(k,1) & p(k,2) & \cdots & p(k,k) \end{array} \right) \] ここで \(p(i,j)\geq 0\), \(\displaystyle \sum_{j=1}^k p(i,j) = 1\) である。

ある時点 \(t\) において確率変数 \(x^{(t)}\) の取りうる状態空間のそれぞれ確率を行ベクトル \(\vector{\pi}^{(t)}\) で表す。\[ \begin{align*} \vector{\pi}^{(t)} & = (\pi^{(t)}_1,\pi^{(t)}_2, \ldots, \pi^{(t)}_k) \\ & = \left(P(x^{(t)}=1),P(x^{(t)}=2),\ldots,P(x^{(t)}=k)\right) \end{align*} \]

\(t+1\) 時点で確率変数 \(x\) が \(j\) である確率は以下のように表される。\[ \begin{align*} \pi^{(t+1)}_j & = P(x^{(t+1)}=j) = \sum_{i=1}^k P(x^{(t)}=i,x^{(t+1)}=j) \\ & = \sum_{i=1}^k P(x^{(t)}=i) P(x^{(t+1)}=j|x^{(t)}=i) \\ & = \sum_{i=1}^k \pi^{(t)}_i p(i,j) \end{align*} \] \[ \begin{align*} \vector{\pi}^{(t+1)} & = \vector{\pi}^{(t)} \vector{T} = \vector{\pi}^{(t-1)} \vector{T}^2 = \cdots \\ & = \vector{\pi}^{(0)} \vector{T}^t \end{align*} \] よってマルコフ連鎖の確率的振る舞いは初期分布 \(\vector{\pi}^{(0)}\) と遷移行列 \(\vector{T}\) によって完全に決定する。

既約性 (irreduciiblity)

到達不能な状態が存在しない性質。任意の状態 \(i\) と \(j\) について、\(i\) から \(j\) へ有限回のステップでたどり着くことができるときマルコフ連鎖は既約である。

以下の推移行列 \(\vector{T}\) は、状態 2 から状態 1 へは移ることができるが状態 1 から状態 2 へはたどり着くことができないため既約ではない。\[ \vector{T} = \left( \begin{array}{cc} 1 & 0 \\ 0.6 & 0.4 \end{array} \right) \]

非周期性 (aperiodicity)

推移行列において元の状態に戻るまでに必要なそれぞれの要素のステップ数の最大公約数が 1 の時、連鎖は非周期性である。

以下の推移行列 \(\vector{T}\) はステップ 2 で元の状態へ戻るため非周期ではない。\[ \vector{T} = \left(\begin{array}{cc}0 & 1 \\ 1 & 0\end{array}\right) \]

不変分布 (invariant distribution)

推移行列 \(\vector{T}\) のマルコフ連鎖に対して行ベクトル \(\vector{\pi} = (\pi_1,\ldots,\pi_k)\) が以下の条件をみたすとき \(\vector{\pi}\) は \(\vector{T}\) の不変分布である。\[ \pi_i \leq 0, \ \ \sum_{i=1}^k \pi_k = 1 \\ \vector{\pi} = \vector{\pi} \vector{T} \]

マルコフ連鎖が規約性と周期性を満たすとき、不変分布が一意に存在し \(\vector{\pi}^{(t)}\) は不変分布 \(\vector{\pi}\) に収束する。

参考文献