マルコフ連鎖のソースを表示

{{出典の明記|date=2018年1月}}
'''マルコフ連鎖'''（マルコフれんさ、{{lang-en-short|Markov chain}}）とは、[[確率過程]]の一種である[[マルコフ過程]]のうち、とりうる状態が離散的（[[有限集合|有限]]または[[可算]]）なもの（離散状態マルコフ過程）をいう。また特に、[[時間]]が離散的なもの（時刻は添え字で表される）を指すことが多い{{Efn|他に連続時間マルコフ過程というものもあり、これは時刻が連続である。}}。マルコフ連鎖は、未来の挙動が現在の値だけで決定され、過去の挙動と無関係である（[[マルコフ性]]）。各時刻において起こる状態変化（'''[[遷移]]'''または推移）に関して、マルコフ連鎖は遷移[[確率]]が過去の状態によらず、現在の状態のみによる系列である。特に重要な確率過程として、様々な分野に応用される。

==定義==
マルコフ連鎖は、一連の[[確率変数]] ''X''<sub>1</sub>, ''X''<sub>2</sub>, ''X''<sub>3</sub>, ... で、現在の状態が決まっていれば、過去および未来の状態は[[独立 (確率論)|独立]]であるものである。形式的には、

:<math>\Pr(X_{n+1}=x|X_n=x_n, \ldots, X_1=x_1, X_0=x_0) = 
\Pr(X_{n+1}=x|X_n=x_n)\,</math>

''X''<sub>i</sub> のとりうる値は、連鎖の'''状態空間'''と呼ばれ、[[可算集合]]''S'' をなす。マルコフ連鎖は[[有向グラフ]]で表現され、エッジにはある状態から他の状態へ遷移する確率を表示する。

マルコフ連鎖の一例に[[有限状態機械]]がある。これは、時刻''n''  において状態
''y'' にあるとすると、それが時刻''n''&nbsp;+&nbsp;1 において状態''x'' に動く確率は、現在の状態にだけ依存し、時刻''n'' には依存しない。

'''時間的に均一な'''（'''斉時的'''）'''マルコフ連鎖'''とは、すべての''n'' に対し

:<math>\Pr(X_{n+1}=x|X_n=y) = \Pr(X_{n}=x|X_{n-1}=y)\,</math>

であるような過程をいう。一般の、時間的に均一でないマルコフ連鎖は、この等式を満たさない。

==マルコフ連鎖の性質==
初期状態''i'' から時刻''n'' で状態''j'' に移る確率は、

:<math>p_{ij}^{(n)} = \Pr(X_n=j\mid X_0=i) \,</math>

で定義され、単一段階の遷移は

:<math>p_{ij} = \Pr(X_1=j\mid X_0=i) \,</math>

で定義される。''n''-段階遷移は、任意の 0<''k''<''n'' に対して次の'''チャップマン・コルモゴロフの等式'''を満たす：

:<math>p_{ij}^{(n)} = \sum_{r \in S} p_{ir}^{(k)} p_{rj}^{(n-k)}</math>

時刻''n'' での状態に関する確率（[[周辺確率]]）は次のように書ける：

: <math> \Pr(X_{n}=j) = \sum_{r \in S} p_{rj} \Pr(X_{n-1}=r) = \sum_{r \in S} p_{rj}^{(n)} \Pr(X_0=r)</math>

ここで右上付き添え字 <math>(n)</math> は整数値である。もしマルコフ連鎖が時間に対して定常的ならば、この添え字は"n乗"という意味にとってもよい（下記参照）。

===可約性===
いま状態''i'' にあるとして、未来のある時点で状態''j'' にある確率が 0 でない
ならば、状態''j'' は状態''i'' （''i'' &rarr; ''j''）から'''到達可能'''
（accessible）といわれる。つまり次のような''n'' があるということである：

: <math> \Pr(X_{n}=j | X_0=i) > 0\, </math>

状態''i'' と状態''j'' が互いに到達可能ならば、状態''i'' と状態''j'' （''i'' &harr; ''j''）は'''連結'''（communicate）しているという。状態の集合''C'' のいずれの対も互いに連結しているならば、''C'' は'''連結類'''（communicating class）という（この連結類は[[同値類]]である）。連結類を出る確率が0ならば、連結類は'''閉じている'''（closed）という。つまり''i'' が''C'' の要素であり''j'' がそうでないならば、''j'' は''i'' から到達可能ではない。

状態空間が連結類ならば、マルコフ連鎖は'''既約'''（または可約でない：irreducible）という。つまり既約なマルコフ連鎖では、任意の状態から任意の状態へ移ることができる。

===周期性===
状態''i'' への回帰が''k'' の倍数回のみに見られ、しかも''k'' がこの性質を持つ最大の数ならば、「状態''i'' の'''[[周期]]'''は''k'' である」という。例えば、''i'' への回帰が偶数回目にのみ起こるならば、''i'' の周期は2である。
形式的には、ある状態の周期は次のように定義される：

: <math> k = \operatorname{gcd}\{ n: \Pr(X_n = i | X_0 = i) > 0\}</math>

（ここで "gcd" は[[最大公約数]]のこと）
''k'' = 1 ならば、状態は'''非周期的'''であるという。連結類の各状態は同じ周期を持たねばならない。

既約なマルコフ連鎖は、状態が非周期的ならば、'''[[エルゴード的]]'''（ergodic）という。

===再帰性===
状態''i'' から開始するとして、「決して''i'' には戻らない」確率が 0 でないならば、状態''i'' は'''一時的'''（transient）という。形式的には、確率変数 ''T<sub>i</sub>'' を次に状態''i'' へ帰る時刻（到達時間）：

: <math>T_i = \operatorname{min}\{n: X_n=i | X_0=i\}</math>

として、「''T<sub>i</sub>'' が有限でない」確率が 0 でないならば、状態''i'' は一時的である：

: <math> \Pr(T_i < \infty) < 1</math>

状態''i'' は、一時的でない（状態iからiに戻る確率 1 で有限な到達時間を持つ）ならば、'''再帰的'''（recurrentまたはpersistent）という。

到達時間が有限でも、その[[平均値]]が有限であるとは限らない。

===定常状態と極限分布===
時間的に一様なマルコフ連鎖で、過程が時間に依存しない行列 <math>p_{ij}</math> で記述でき、ベクトル ''&pi;'' の要素 ''&pi;<sub>j</sub>'' 
の和が 1 で、次を満たすとする：

: <math>\pi_j = \sum_{i \in S} \pi_i p_{ij}</math>

この場合には、ベクトル ''&pi;'' を'''定常分布'''という。既約な連鎖は、そのすべての状態が再帰的ならば、またその場合に限り、定常分布を持つ。この場合、''&pi;'' はただ1つで、再帰時間の[[期待値]] ''M<sub>j</sub>'' との間に次の関係がある：

: <math>\pi_j = \frac{1}{M_j}</math>

さらに、連鎖が既約かつ非周期的ならば、任意の''i'' と''j'' に対して

: <math>\lim_{n \rarr \infty} p_{ij}^{(n)} = \frac{1}{M_j}</math>

となる。ここでは初期分布に関して何も仮定していない。つまり連鎖は初期の状態によらず定常分布に収束し，これを連鎖の'''均衡分布'''という。

連鎖が既約でないならば、その定常分布はただ1つに定まらない。（閉じた連結類を考えれば、各連結類毎にただ1つの定常分布がある。）しかし、状態 ''j'' が非周期的ならば、

: <math>\lim_{n \rarr \infty} p_{jj}^{(n)} = \frac{1}{M_j}</math>

であり、他の任意の状態''i'' に対し''i'' を初期状態として、連鎖が状態''j'' に到達する確率を''f<sub>ij</sub>'' とすると、

: <math>\lim_{n \rarr \infty} p_{ij}^{(n)} = \frac{f_{ij}}{M_j}</math>

となる。

==有限状態マルコフ連鎖==
状態空間が有限ならば、遷移確率分布は[[行列]]で表現され、これは'''遷移行列'''（transition matrix）と呼ばれる。この行列'''P'''の第(''i'', ''j'')要素は

:<math>p_{ij} = \Pr(X_{n+1}=j\mid X_n=i) \,</math>

に等しい。さらに、マルコフ連鎖が時間的に均一、つまり遷移行列'''P'''が添え字
''n'' によらないならば、''k''-段階遷移確率は遷移行列の''k''乗、つまり'''P'''<sup>''k''</sup> と書ける。

定常分布''&pi;'' は行ベクトルで、次の式を満たす：

:<math> \pi = \pi\mathbf{P}\,</math>

言い換えると、定常分布''&pi;'' は遷移行列の正規化された左側[[固有ベクトル]]で、その[[固有値]]は 1 である。

もしくは''&pi;'' を、行列'''P'''に対応する単位[[単体 (数学)|単体]]上の線形（連続）変換での不動点と見ることもできる。単位単体上の任意の連続変換は不動点を持つから、定常分布は必ず存在するが、一般にただ1つであるという保証はない。しかし、マルコフ連鎖が既約かつ非周期的ならば、定常分布'''&pi;'''がただ1つ存在する。

さらに'''P'''<sup>''k''</sup>が、各行が定常分布'''&pi;'''であるような行列に収束するならば、

:<math>\lim_{k\rightarrow\infty}\mathbf{P}^k=\mathbf{1}\pi</math>
（ここで'''1'''はすべての成分が1である列ベクトル）となる（[[ペロン・フロベニウスの定理]]）。つまり、時間が経つにつれてマルコフ連鎖は、初期分布に関わりなく、定常分布に収束するということである。

マルコフ連鎖は、次で示される''&pi;''：

:<math>\pi_i p_{i,j} = \pi_j p_{j,i}</math>

が存在するならば、'''可逆'''（reversible）であるという。可逆マルコフ連鎖では、''&pi;'' は常に定常分布である。

マルコフ連鎖の特別な場合で、遷移確率行列の行がすべて同じであるものを、[[ベルヌーイ系]]（Bernoulli scheme）という。これは次の状態が現在の状態からも独立ということである。さらに可能な状態が2つしかないベルヌーイ系が、[[ベルヌーイ過程]]（[[ベルヌーイ試行]]を連続して行うもの）である。

==連続時間マルコフ連鎖==
連続時間に対するマルコフ過程は、微小な時間変化''h'' を用いて次のように定義される：

:<math>\Pr(X(t+h) = j | X(t) = i) = q_{ij}h + o(h)\,</math>

ただしここで''o(h)'' とは、''h'' が0となる極限で''h'' より速く0に近づく項を表す。またここで''h'' = 1とおけば、普通のマルコフ連鎖と同じ形になる。

この連続時間マルコフ過程から離散的に取り出した系列が、連続時間マルコフ連鎖である。

==N階マルコフ連鎖と単純マルコフ連鎖==
次の状態が現在を含めた過去N個の状態履歴に依存して決まる確率過程を、'''N階マルコフ連鎖'''（もしくは、N重マルコフ連鎖、N次マルコフ連鎖）という。
これに対して、N=1の通常のマルコフ連鎖は'''単純マルコフ連鎖'''と呼ばれることがある。

N階マルコフ連鎖は、形式的には次のような確率過程である。

:<math>\Pr(X_{n+1}=x|X_n=x_n, \ldots, X_0=x_0) = 
\Pr(X_{n+1}=x|X_n=x_n,X_{n-1}=x_{n-1},\ldots,X_{n-N+1}=x_{n-N+1})\,</math>

どんなN階マルコフ連鎖も、N個の状態組を新たな状態空間とすることによって、単純マルコフ連鎖として表現することができる。
このため、単純マルコフ連鎖で成立する性質は、N階マルコフ連鎖でもそのまま成立する。

==応用==
マルコフ系は[[物理学]]、とりわけ[[統計力学]]にしばしば現れる。ここでは、
[[力学]]が時間に対して不変であると想定され、また履歴を考慮する必要がないと想定される場合に、詳細が不明またはモデル化できないために確率過程が用いられる。

マルコフ連鎖はまた[[待ち行列理論]]や[[統計学]]でモデル化に用いられる。

[[クロード・シャノン]]が[[情報理論]]を創始した論文"A mathematical theory of communication"（[[通信の数学的理論]]）では、マルコフ連鎖を利用して[[エントロピー]]の概念を導入している。さらにこのような方法は、[[データ圧縮]]や[[パターン認識]]に応用されている。

マルコフ連鎖は[[強化学習]]でも重要である。

[[Google]]に使われている[[PageRank]]もマルコフ連鎖によって定義される。

遷移確率が初め不明でデータからそれを見積らなければならない場合には、[[隠れマルコフモデル]]が用いられ、これは[[音声認識]]や[[バイオインフォマティクス]]（[[塩基配列]]からの[[遺伝子]]の探索など）にも広く用いられている。

==脚注==
===注釈===
{{Notelist}}

== 関連項目 ==
* [[マルコフ過程]]
* [[マルコフ決定過程]]
* [[マルコフ再生過程]]
* [[マルコフ連鎖モンテカルロ法]]
* [[アンドレイ・マルコフ]]
* [[隠れマルコフモデル]]
* [[人工知能]]
* [[ベイズの定理]]
* [[マスター方程式]]

== 外部リンク ==
* {{MathWorld|title=Markov Chain|urlname=MarkovChain}}

{{確率論}}
{{Normdaten}}

{{デフォルトソート:まるこふれんさ}}
[[Category:確率論]]
[[Category:アンドレイ・マルコフ]]
[[Category:数学のエポニム]]
[[Category:数学に関する記事]]