マルコフ連鎖とは何？わかりやすく解説 Weblio辞書

すべての辞書から再検索する

OR事典

索引トップランキングカテゴリー

マルコフ連鎖

読み方：まるこふれんさ
【英】：Markov chain

概要

マルコフ性をもつ離散状態空間上の確率過程. すなわち, 確率過程 $\{ X(t) \}\,$ が, 任意の $s, t\,$ と $i,j\,$ に対して

$\mbox{P}(X(s+t)\,$	$=j\|X(u), \; 0 \leq u < s, X(s)=i)\,$
	$= \mbox{P}(X(s+t)=j\|X(s)=i)\,$

を満たす場合, マルコフ連鎖と呼ぶ.

詳説

マルコフ過程　独立性を緩めた性質であるマルコフ性を持つ確率過程のことをマルコフ過程と呼び, その中で状態が離散的なものを一般にマルコフ連鎖と呼ぶ. マルコフ連鎖は最も基本的で応用範囲の広い\確率過程の一つである.

離散時間マルコフ連鎖　離散的な状態空間 ${\mathcal S}\,$ 上の確率過程 $\{ X_n; \; n=0,1,2,\cdots \}\,$ が, 任意の時点 $n\,$ , $m\,$ と任意の状態 $i_0, \cdots, i_m, j \in {\mathcal S}\,$ に対して

$\mathrm{P}(X_{m+n}=j|X_k=i_k, k=m,m-1,\cdots,0) =\mathrm{P}(X_{m+n}=j|X_m=i_m)$ 　　　　　 $(1)\,$

を満たすとき, $\{ X_n \}\,$ を離散時間マルコフ連鎖と呼ぶ. (1) は, 将来の分布が現在の状態のみで定まり, 過去の状態には依存しない性質を表しており, マルコフ性と呼ばれる.賭けの問題における所持金の推移や, 在庫理論における各期の在庫量の変化など, マルコフ性を持つと考えられる例は多い.

　(1) の推移確率が, 時点 $m\,$ に依存しない場合, マルコフ連鎖は斉時的であるという. 斉時的な離散時間マルコフ連鎖 $\{ X_n \}\,$ に対して, $p_{ij}(n)=\mathrm{P}(X_{m+n}=j|X_m=i)\,$ を $n\,$ ステップ推移確率, $\boldsymbol{P}(n)=(p_{ij}(n))\,$ を $n\,$ ステップ推移確率行列と呼ぶ. 特に 1ステップ推移確率を $p_{ij}\,$ で表し, $\boldsymbol{P}=(p_{ij})\,$ を推移確率行列と呼ぶ. チャップマン・コルモゴロフの等式 (Chapman-Kolmogorov equation) $\boldsymbol{P}(m+n)=\boldsymbol{P}(m) \boldsymbol{P}(n)$ から $\boldsymbol{P}(n)=\boldsymbol{P}^n$ が成り立つので, 1 ステップ推移確率行列 $\boldsymbol{P}$ が与えられれば, 任意のステップの推移確率を計算することができる.

既約なマルコフ連鎖と吸収的マルコフ連鎖　状態の組 $i, j\,$ に対して, 適当な $n\,$ で $p_{ij}(n)>0\,$ となる場合, $i\,$ から $j\,$ へ到達可能であるという. 任意の状態から他のどの状態へも到達可能であるマルコフ連鎖は既約であるという. 一方, $p_{ii}=1\,$ である状態 $i\,$ は, 一度入ると他の状態へ推移できないため吸収状態と呼ばれる. 任意の状態から出発したとき確率1でいつかはいずれかの吸収状態に到達するマルコフ連鎖を吸収的という. 後述するように, 既約なマルコフ連鎖では長期間観察したときに各状態に滞在する時間の割合が主な分析対象となる. これに対し, 吸収的マルコフ連鎖では, 吸収されるまでの挙動, 例えば吸収時間の分布, 吸収までに各状態に滞在する平均ステップ数, 複数の吸収状態がある場合に各状態への吸収確率, などが分析の対象となる.

　 $p_{ii}(n)>0\,$ となるすべての $n \geq 1\,$ の最大公約数を, 状態 $i\,$ の周期と定める. 既約なマルコフ連鎖では, すべての状態は同じ周期を持つことが知られている. また, 周期 1 のマルコフ連鎖を非周期的という.

　 $i\,$ から $j\,$ への初到達時間を $T_{ij}\,$ とすると, マルコフ連鎖の各状態 ( $i\,$ とする) はその状態への再帰確率 $\mathrm{P}(T_{ii}<\infty)\,$ と平均再帰時間 $\mathrm{E}(T_{ii})\,$ により以下のように分類される.

$\left\{ \begin{array}{l} \\ \\ \\ \end{array} \right.$	一時的　　 $\mathrm{P}(T_{ii}<\infty)<1 \,$
	再帰的　　 $\mathrm{P}(T_{ii}<\infty)=1\,$	$\left\{ \begin{array}{ll} \\ \\ \\ \end{array} \right.$	零再帰的　　 $\mathrm{E}(T_{ii}) = \infty \,$
			正再帰的　　 $\mathrm{E}(T_{ii}) < \infty \,$

なお, 既約なマルコフ連鎖ではすべての状態は同じ分類に属するので, これらはマルコフ連鎖自身の分類でもある. 特に, 既約で非周期的かつ正再帰的なマルコフ連鎖は, エルゴード的マルコフ連鎖と呼ばれる.

定常分布　 $n \rightarrow \infty\,$ のとき $p_{ij}(n)\,$ が初期状態 $i\,$ に無関係な正定数 $\pi_j\,$ に収束し, 正規化条件 $\textstyle \sum_{j \in {\mathcal S}} \pi_j = 1\,$ を満たす場合, $\boldsymbol{\pi}=(\pi_j)\,$ を極限分布と呼ぶ. 極限分布は平衡方程式 $\boldsymbol{\pi}=\boldsymbol{\pi}\boldsymbol{P}\,$ を満たすため, この方程式と正規化条件から求めることができる. 極限分布に対して, 平衡方程式を満たす確率分布を定常分布と呼ぶ. 極限分布は定常分布であるが, 周期的なマルコフ連鎖のように定常分布は必ずしも極限分布とならない. 既約で非周期的なマルコフ連鎖に対しては, (1) 正再帰的であること, (2) 極限分布が存在すること, (3) 平衡方程式と正規化条件が一意の解を持つこと, の3条件は同値となる. 実際, エルゴード的なマルコフ連鎖では $\pi_j = 1/\mathrm{E}(T_{jj})\,$ となり, 極限分布は $\{ X_n \}\,$ を長時間観測したときに各状態に滞在する時間の割合に一致する. なお, 有限状態のマルコフ連鎖が既約で非周期的であれば, 必ず正再帰的となる. 一方, 状態 $j\,$ が一時的もしくは零再帰的ならば, $\textstyle \lim_{n \rightarrow \infty} p_{ij}(n)=0\,$ となり極限分布は存在しない.

連続時間マルコフ連鎖　離散状態空間上の連続時間確率過程 $\{ X(t); \; t \geq 0 \}\,$ が, 任意の時点 $s\,$ , $t\,$ と状態 $i, j\,$ , および履歴 $x(u)\,$ に対して

$\mathrm{P}(X(s+t)=j|X(u)=x(u), 0 \leq u \leq s) =\mathrm{P}(X(s+t)=j|X(s)=x(s))$ 　　　　　 $(2)\,$

を満たすとき, 連続時間マルコフ連鎖と呼ぶ. ポアソン過程や出生死滅過程などは, 代表的な連続時間マルコフ連鎖である.

　離散時間の場合と同様に, (2) が $s\,$ に依存しないマルコフ連鎖を斉時的といい, 推移確率を $p_{ij}(t) = \mathrm{P}(X(s+t)=j|X(s)=i)\,$ , 推移確率行列を $\boldsymbol{P}(t)\,$ で表す. 異なる状態 $i, j\,$ に対して, $\textstyle q_{ij} = \lim_{h \downarrow 0} h^{-1} p_{ij}(h)\,$ を状態 $i\,$ から $j\,$ への推移速度といい, $q_{ij}\,$ を非対角要素, 対角要素を $\textstyle q_{ii}=-\sum_{j \neq i} q_{ij}\,$ とする行列 $\boldsymbol{Q}=(q_{ij})\,$ を推移速度行列と呼ぶ. マルコフ性から, 連続時間マルコフ連鎖が状態 $i\,$ に滞在する時間はパラメータ $-q_{ii}\,$ の指数分布に従う. また, $-q_{ij}/q_{ii}\,$ は状態 $i\,$ での滞在が終了したという条件の下で, 推移先が $j\,$ である条件付き確率を与える. 推移速度行列 $\boldsymbol{Q}\,$ が与えられると, 推移確率はコルモゴロフの後退方程式 $\boldsymbol{P}'(t)=\boldsymbol{Q}\boldsymbol{P}(t)\,$ , あるいはコルモゴロフの前進方程式 $\boldsymbol{P}'(t)=\boldsymbol{P}(t)\boldsymbol{Q}\,$ によって特徴付けられる. この関係から, 応用上現れる多くのマルコフ連鎖では推移確率が $\boldsymbol{P}(t) = \mbox{exp}( \boldsymbol{Q}t )\ (t \geq 0)\,$ で表される.

　離散時間マルコフ連鎖と同様に, 任意の状態から他のどの状態へも推移可能な場合, このマルコフ連鎖は既約であるという. また, 状態の分類 (一時的, 零再帰的, 正再帰的) も, 各状態への再帰時間 $T_{ii}\,$ の性質により離散時間マルコフ連鎖の場合と同様に定義される. 極限分布についても, 初期状態 $i\,$ に無関係に $\textstyle \lim_{t \rightarrow \infty}p_{ij}(t) = \pi_j>0\,$ と収束し, $\textstyle \sum_{j \in {\mathcal S}} \pi_j = 1\,$ が成り立つ場合, $\boldsymbol{\pi}=(\pi_j)\,$ を極限分布とよぶ. 極限分布は, 平衡方程式 $\boldsymbol{0} = \boldsymbol{\pi}\boldsymbol{Q}\,$ と正規化条件 $\textstyle \sum_{i \in {\mathcal S}} \pi_i = 1\,$ から求めることができる. 既約な連続時間マルコフ連鎖に対しては, 正再帰的であること, 極限分布が存在すること, 平衡方程式と正規化条件を満たす $\pi_j\,$ が存在すること, の3条件は同値である.

マルコフ連鎖の一般化　マルコフ性は独立性を少し緩めた概念だが, 適用範囲は広い. 例えば, 離散時間確率過程 $\{ X_n \}\,$ の将来の時点における分布が, 現在の状態 $X_n\,$ と過去の $k\,$ 状態 $X_{n-1}, \cdots, X_{n-k}\,$ に依存する場合, $\{ X_n \}\,$ 自身はマルコフ連鎖とならないが, $Y_n=(X_{n-k}, \cdots, X_n)\,$ はマルコフ連鎖となる. また, 状態の推移はマルコフ連鎖に従い, 各状態の滞在時間分布が一般分布に拡張された確率過程はセミマルコフ過程と呼ばれ, マルコフ連鎖による分析が援用できる.さらに, そのままではマルコフ性を持たない確率過程に対しても, 隠れマルコフ連鎖法や補助変数法を利用することでマルコフ連鎖としてモデル化できる場合が少なくない. このようなモデル化における汎用性・柔軟性は, マルコフ連鎖が広く利用される大きな理由となっている.

参考文献

[1] K. L. Chang,　Markov Chains with Stationary Transition Probabilities,　Springer-Verlag, 1967.

[2] D. Freedman,　Markov Chains,　Springer, 1983.

[3] J. G. Kemenny and J. L. Snell,　Finite Markov Chain,　Van Nostrand, 1960.

[4] 森村英典, 高橋幸雄, 『マルコフ解析』, 日科技連, 1979.

「OR事典」の他の用語

待ち行列：	ポーリングモデルマルコフ型到着過程マルコフ性マルコフ連鎖ランダム順サービスリトルの公式リンドレーの方程式
確率と確率過程：	マルコフ変調ポアソン過程マルコフ性マルコフ決定過程マルコフ連鎖マルコフ連鎖の数値解法マルコフ過程マルチンゲール
待ち行列ネットワーク：	ポアソン到着ポアソン過程ポーリングモデルマルコフ連鎖マルコフ過程マーク付き点過程リトルの公式