マルコフ連鎖

マルコフ連鎖（マルコフれんさ、（英: Markov chain）は状態空間が高々可算集合なマルコフ過程である。すなわち、取りうる状態が離散的かつ未来の状態が過去の状態履歴に影響されない確率過程である。マルコフ鎖（マルコフさ）とも。

概要

マルコフ連鎖とは、確率過程の一種であるマルコフ過程のうち、とりうる状態が離散的（有限または可算）なものをいう（⇒ #定義）。すなわち離散状態マルコフ過程を指す。

マルコフ連鎖は、未来の挙動が現在の値だけで決定され、過去の挙動と無関係である（マルコフ性）。各時刻において起こる状態変化（遷移または推移）に関して、マルコフ連鎖は遷移確率が過去の状態によらず、現在の状態のみによる系列である。特に重要な確率過程として、様々な分野に応用される。

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

定義

マルコフ連鎖は、一連の確率変数 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 をなす。マルコフ連鎖は有向グラフで表現され、エッジにはある状態から他の状態へ遷移する確率を表示する。

性質

初期状態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 に対して

$\lim _{n\rightarrow \infty }p_{ij}^{(n)}={\frac {1}{M_{j}}}$

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

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

$\lim _{n\rightarrow \infty }p_{jj}^{(n)}={\frac {1}{M_{j}}}$

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

$\lim _{n\rightarrow \infty }p_{ij}^{(n)}={\frac {f_{ij}}{M_{j}}}$

となる。

分類

マルコフ連鎖は更なる制約により以下のように分類される：

• 時間の連続性
  • 連続時間マルコフ連鎖
  • 離散時間マルコフ連鎖
• 状態空間の濃度
  • 有限状態マルコフ連鎖
• 遷移の時間変化
  • 斉時マルコフ連鎖
• 遷移の状態依存性
  • ベルヌーイ系

有限状態マルコフ連鎖

→「確率行列」も参照

有限状態マルコフ連鎖（ゆうげんじょうたいマルコフれんさ、（英: finite-state Markov chain）は状態空間が有限集合なマルコフ連鎖である。有限マルコフ連鎖（ゆうげんマルコフれんさ、（英: finite Markov chain）とも。

マルコフ連鎖は状態空間が高々可算集合であり、状態が可算無限個の場合がある。有限状態マルコフ連鎖では状態空間 $\textstyle S$ の濃度 $\textstyle |S|$ が有限、すなわち状態が有限個である。よって時刻 $\textstyle t$ における状態の確率質量は有限次元数ベクトルを用いた確率ベクトル $\textstyle {\boldsymbol {p}}_{t}\in [0,1]^{|S|}$ で表現できる。

有限状態マルコフ連鎖はマルコフ性をもち、かつ、遷移時に有限次元数ベクトルである $\textstyle {\boldsymbol {p}}_{t}$ を $\textstyle {\boldsymbol {p}}_{t+1}$ へ移す。よってこの遷移を $\textstyle t$ における確率行列 $\textstyle \mathbf {P} _{t}\in [0,1]^{|S|\times |S|}$ で表現できる。有限状態マルコフ連鎖の文脈では $\textstyle \mathbf {P} _{t}$ を遷移行列（せんいぎょうれつ）、遷移確率行列（せんいかくりつぎょうれつ）と呼ぶ。

離散時間有限状態マルコフ連鎖は有限状態マルコフ連鎖の一種であり、$\textstyle {\boldsymbol {p}}_{t+1}={\boldsymbol {p}}_{0}\prod _{k=0}^{t}\mathbf {P} _{k}$ で表現できる。

可逆マルコフ連鎖

マルコフ連鎖は、次で示されるπ：

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

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

連続時間マルコフ連鎖

連続時間マルコフ連鎖（れんぞくじかんマルコフれんさ、（英: continuous-time Markov chain; CTMC）は状態空間が高々可算集合な連続時間マルコフ過程である。

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

$\Pr(X(t+h)=j|X(t)=i)=q_{ij}h+o(h)\,$

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

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

離散時間マルコフ連鎖

離散時間マルコフ連鎖（りさんじかんマルコフれんさ、（英: discrete-time Markov chain; DTMC）は状態空間が高々可算集合な離散時間マルコフ過程である。

離散時間有限状態マルコフ連鎖

離散時間有限状態マルコフ連鎖は時間が離散的で状態空間が有限集合なマルコフ連鎖である。

離散時間有限状態マルコフ連鎖は有限状態マルコフ連鎖であるため、状態を確率ベクトル $\textstyle {\boldsymbol {p}}_{t}$、遷移を遷移行列 $\textstyle \mathbf {P} _{t}$ で表現できる。また離散時間有限状態マルコフ連鎖は離散時間マルコフ連鎖であるため、遷移の連続を積で表現できる。そのため離散時間有限状態マルコフ連鎖は、行列の連鎖乗積を用いて、

${\boldsymbol {p}}_{t+1}={\boldsymbol {p}}_{t}\mathbf {P} _{t}={\boldsymbol {p}}_{t-1}\mathbf {P} _{t-1}\mathbf {P} _{t}=\cdots ={\boldsymbol {p}}_{0}\mathbf {P} _{0}\mathbf {P} _{1}\mathbf {P} _{2}\ldots \mathbf {P} _{t}\ =\ {\boldsymbol {p}}_{0}\prod _{k=0}^{t}\mathbf {P} _{k}$

で表現できる。

斉時マルコフ連鎖

斉時マルコフ連鎖（せいじマルコフれんさ、（英: time-homogeneous Markov chain）は、すべてのn に対し

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

であるような過程をいう。斉時的マルコフ連鎖、時間的に均一なマルコフ連鎖、斉次マルコフ連鎖（せいじマルコフれんさ、（英: homogeneous Markov chain）とも。

斉時性が保証されないマルコフ連鎖は非斉時マルコフ連鎖とも呼ばれる。

斉時有限状態マルコフ連鎖

斉時有限状態マルコフ連鎖は状態空間が有限集合な斉時マルコフ連鎖である。

斉時有限状態マルコフ連鎖は有限状態であるため遷移行列 $\textstyle \mathbf {P}$ で表現でき、かつ、斉時であるため $\textstyle \mathbf {P}$ が時間に依らず一定である（添え字 n によらない）。よって $\textstyle k$-段階遷移確率は行列の冪を用いて $\textstyle \mathbf {P} ^{k}$ と表現できる。

定常分布

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

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

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

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

さらにP^kが、各行が定常分布πであるような行列に収束するならば、

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

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

ベルヌーイ系

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

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もマルコフ連鎖によって定義される。

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

脚注

参考文献

• 秋田, 智之 (2014). “有限状態マルコフ連鎖モデルにおける状態分布の将来予測と推定精度” (PDF). 2014年度 統計関連学会連合大会 講演プログラム: 1.
• 永幡, 幸生 (2021), マルコフ連鎖入門 第 1 回, 新潟大学講義『マルコフ連鎖入門』, 新潟大学, https://www.eng.niigata-u.ac.jp/~nagahata/lecture/2021/master/daigakuin-f-1.pdf 

関連項目

• 確率過程
  • マルコフ過程
    • マルコフ連鎖
      • 有限状態マルコフ連鎖
      • 連続時間マルコフ連鎖 / 離散時間マルコフ連鎖
• マルコフ再生過程
• 状態空間 (確率過程)
• 確率行列
• マルコフ決定過程
• 隠れマルコフモデル
• マルコフ連鎖モンテカルロ法
• 人工知能
• ベイズの定理
• マスター方程式

外部リンク

• Weisstein, Eric W. “Markov Chain”. mathworld.wolfram.com (英語).