マルコフ連鎖

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

定義

マルコフ連鎖は、一連の確率変数 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 から到達可能ではない。状態空間が連結類ならば、マルコフ連鎖は既約︵または可約でない‥irreducible︶という。つまり既約なマルコフ連鎖では、任意の状態から任意の状態へ移ることができる。

周期性

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

k=\operatorname {gcd} \{n:\Pr(X_{n}=i|X_{0}=i)>0\}

︵ここで "gcd" は最大公約数のこと︶ k = 1 ならば、状態は非周期的であるという。連結類の各状態は同じ周期を持たねばならない。既約なマルコフ連鎖は、状態が非周期的ならば、エルゴード的︵ergodic︶という。

再帰性

状態i から開始するとして、﹁決してi には戻らない﹂確率が 0 でないならば、状態i は一時的︵transient︶という。形式的には、確率変数 T_iを次に状態i へ帰る時刻︵到達時間︶‥

T_{i}=\operatorname {min} \{n:X_{n}=i|X_{0}=i\}

として、﹁T_i が有限でない﹂確率が 0 でないならば、状態i は一時的である‥

\Pr(T_{i}<\infty )<1

状態i は、一時的でない︵状態iからiに戻る確率1で有限な到達時間を持つ︶ならば、再帰的︵recurrentまたはpersistent︶という。到達時間が有限でも、その平均値が有限であるとは限らない。

定常状態と極限分布

時間的に一様なマルコフ連鎖で、過程が時間に依存しない行列

p_{ij}

で記述でき、ベクトル π の要素 π_j の和が1で、次を満たすとする‥

\pi _{j}=\sum _{i\in S}\pi _{i}p_{ij}

この場合には、ベクトル π を定常分布という。既約な連鎖は、そのすべての状態が再帰的ならば、またその場合に限り、定常分布を持つ。この場合、π はただ1つで、再帰時間の期待値 M_jとの間に次の関係がある‥

\pi _{j}={\frac {1}{M_{j}}}

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

{\displaystyle \lim _{n\rightarrow \infty }p_{ij}^{(

となる。ここでは初期分布に関して何も仮定していない。つまり連鎖は初期の状態によらず定常分布に収束し，これを連鎖の均衡分布という。連鎖が既約でないならば、その定常分布はただ1つに定まらない。︵閉じた連結類を考えれば、各連結類毎にただ1つの定常分布がある。︶しかし、状態 jが非周期的ならば、

{\displaystyle \lim _{n\rightarrow \infty }p_{jj}^{(

であり、他の任意の状態i に対しi を初期状態として、連鎖が状態j に到達する確率をf_ij とすると、

{\displaystyle \lim _{n\rightarrow \infty }p_{ij}^{(

となる。

有限状態マルコフ連鎖

状態空間が有限ならば、遷移確率分布は行列で表現され、これは遷移行列︵transition matrix︶と呼ばれる。この行列Pの第(i, j)要素は

p_{ij}=\Pr(X_{n+1}=j\mid X_{n}=i)\,

に等しい。さらに、マルコフ連鎖が時間的に均一、つまり遷移行列Pが添え字 n によらないならば、k-段階遷移確率は遷移行列のk乗、つまりP^k と書ける。定常分布π は行ベクトルで、次の式を満たす‥

\pi =\pi \mathbf {P} \,

言い換えると、定常分布π は遷移行列の正規化された左側固有ベクトルで、その固有値は1である。もしくはπ を、行列Pに対応する単位単体上の線形︵連続︶変換での不動点と見ることもできる。単位単体上の任意の連続変換は不動点を持つから、定常分布は必ず存在するが、一般にただ1つであるという保証はない。しかし、マルコフ連鎖が既約かつ非周期的ならば、定常分布πがただ1つ存在する。さらにP^kが、各行が定常分布πであるような行列に収束するならば、

\lim _{k\rightarrow \infty }\mathbf {P} ^{k}=\mathbf {1} \pi

︵ここで1はすべての成分が1である列ベクトル︶となる︵ペロン・フロベニウスの定理︶。つまり、時間が経つにつれてマルコフ連鎖は、初期分布に関わりなく、定常分布に収束するということである。マルコフ連鎖は、次で示されるπ‥

\pi _{i}p_{i,j}=\pi _{j}p_{j,i}

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

連続時間マルコフ連鎖

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

{\displaystyle \Pr(X(t+h)=j|X(

ただしここでo(h) とは、h が0となる極限でh より速く0に近づく項を表す。またここでh = 1とおけば、普通のマルコフ連鎖と同じ形になる。この連続時間マルコフ過程から離散的に取り出した系列が、連続時間マルコフ連鎖である。

N階マルコフ連鎖と単純マルコフ連鎖

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

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

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

応用

マルコフ系は物理学、とりわけ統計力学にしばしば現れる。ここでは、力学が時間に対して不変であると想定され、また履歴を考慮する必要がないと想定される場合に、詳細が不明またはモデル化できないために確率過程が用いられる。マルコフ連鎖はまた待ち行列理論や統計学でモデル化に用いられる。クロード・シャノンが情報理論を創始した論文"A mathematical theory of communication"︵通信の数学的理論︶では、マルコフ連鎖を利用してエントロピーの概念を導入している。さらにこのような方法は、データ圧縮やパターン認識に応用されている。マルコフ連鎖は強化学習でも重要である。 Googleに使われているPageRankもマルコフ連鎖によって定義される。遷移確率が初め不明でデータからそれを見積らなければならない場合には、隠れマルコフモデルが用いられ、これは音声認識やバイオインフォマティクス︵塩基配列からの遺伝子の探索など︶にも広く用いられている。

脚注

注釈

^ 他に連続時間マルコフ過程というものもあり、これは時刻が連続である。

外部リンク

Weisstein, Eric W. "Markov Chain". mathworld.wolfram.com (英語).

[1] 他に連続時間マルコフ過程というものもあり、これは時刻が連続である。

[注