マルコフ連鎖とは?

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.


マルコフ連鎖

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2019/03/15 05:28 UTC 版)

マルコフ連鎖(マルコフれんさ、: Markov chain)とは、確率過程の一種であるマルコフ過程のうち、とりうる状態が離散的(有限または可算)なもの(離散状態マルコフ過程)をいう。また特に、時間が離散的なもの(時刻は添え字で表される)を指すことが多い(他に連続時間マルコフ過程というものもあり、これは時刻が連続である)。マルコフ連鎖は、未来の挙動が現在の値だけで決定され、過去の挙動と無関係である(マルコフ性)。各時刻において起こる状態変化(遷移または推移)に関して、マルコフ連鎖は遷移確率が過去の状態によらず、現在の状態のみによる系列である。特に重要な確率過程として、様々な分野に応用される。






「マルコフ連鎖」の続きの解説一覧


英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

「マルコフ連鎖」の関連用語

1
100% |||||




5
100% |||||

6
100% |||||

7
100% |||||

8
100% |||||

9
100% |||||


マルコフ連鎖のお隣キーワード

   

英語⇒日本語
日本語⇒英語
   
検索ランキング



マルコフ連鎖のページの著作権
Weblio 辞書情報提供元は参加元一覧にて確認できます。

  
日本オペレーションズ・リサーチ学会日本オペレーションズ・リサーチ学会
Copyright (C) 2019 (社)日本オペレーションズ・リサーチ学会 All rights reserved.
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアのマルコフ連鎖 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。

©2019 Weblio RSS