マルコフ連鎖

出典: フリー百科事典『ウィキペディア（Wikipedia）』

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

[編集] 定義

マルコフ連鎖は、一連の確率変数 X₁, X₂, X₃, ... で、現在の状態が決まっていれば、過去および未来の状態は独立であるものである。形式的には、

$\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)\,$

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

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

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

$\Pr(X_{n+1}=x|X_n=y) = \Pr(X_{n}=x|X_{n-1}=y)\,$

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

[編集] マルコフ連鎖の性質

初期状態i から時刻n で状態j に移る確率は、

$p_{ij}^{(n)} = \Pr(X_n=j\mid X_0=i) \,$

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

$p_{ij} = \Pr(X_1=j\mid X_0=i) \,$

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

$p_{ij}^{(n)} = \sum_{r \in S} p_{ir}^{(k)} p_{rj}^{(n-k)}$

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

$\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)$

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

[編集] 可約性

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

$\Pr(X_{n}=j | X_0=i) > 0\,$

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