離散時間マルコフ連鎖

確率において、離散時間マルコフ連鎖( DTMC ) は、確率過程と呼ばれるランダム変数のシーケンスであり、次の変数の値は現在の変数の値のみに依存し、過去の変数には依存しません。たとえば、マシンにはAとEという 2 つの状態があります。マシンが状態Aにあるとき、状態Eに移行する可能性は 40% 、状態Aにとどまる可能性は 60% です。マシンが状態Eにあるとき、マシンがAに移行する可能性は 70%、状態Eにとどまる可能性は 30%です。マシンの状態のシーケンスはマルコフ連鎖です。連鎖を で表すと、はマシンの開始状態であり、は 10 回の遷移後の状態を表すランダム変数です。このプロセスは、自然数でインデックス付けされ、永久に継続します。 ${\displaystyle X_{0},X_{1},X_{2},...}$${\displaystyle X_{0}}$${\displaystyle X_{10}}$

マルコフ連鎖ではない確率過程の例としては、状態AとE を持ち、以前にA を訪れたことがある場合には 50% の確率でいずれかの状態からAに移動する機械のモデルが挙げられます(機械がEに移動する確率は 50% または 80% になります)。これは、機械の動作が全体の履歴に依存するためです。機械が E にある場合、過去の値に応じてAに移動する確率は 50% または 20% になります。したがって、マルコフ特性はありません。

マルコフ連鎖は、任意の状態から各状態に移行する確率をリストした確率行列で記述できます。この行列から、将来nステップ後に特定の状態にある確率を計算できます。マルコフ連鎖の状態空間は、相互に到達可能な状態 (1 つの遷移または多数の遷移) を記述する通信クラスに分割できます。各状態は、連鎖がその状態に戻る確率に応じて、一時的または反復的として記述できます。マルコフ連鎖には、周期性、可逆性、定常性などの特性があります。連続時間マルコフ連鎖は離散時間マルコフ連鎖に似ていますが、離散的な時間ステップとしてではなく、時間の経過とともに連続的に状態を移動します。他の確率プロセスは、マルコフ特性、つまり過去の動作がプロセスに影響せず、現在の状態のみに影響するという特性を満たすことができます。

離散時間マルコフ連鎖は、マルコフ特性を持つランダム変数 のシーケンスです。マルコフ特性とは、次の状態に移行する確率が現在の状態のみに依存し、以前の状態には依存しないというものです。 ${\displaystyle X_{0},X_{1},X_{2},...}$

${\displaystyle \Pr(X_{n+1}=x\mid X_{1}=x_{1},X_{2}=x_{2},\ldots ,X_{n}=x_{n})=\Pr(X_{n+1}=x\mid X_{n}=x_{n}),}$両方の条件付き確率が明確に定義されている場合、つまり、${\displaystyle \Pr(X_{1}=x_{1},\ldots ,X_{n}=x_{n})>0.}$

X _iの可能な値は連鎖の状態空間と呼ばれる可算集合 S を形成する。 ^[1]

マルコフ連鎖は、多くの場合、有向グラフのシーケンスによって記述されます。グラフnのエッジには、時刻nのある状態から時刻n  + 1の他の状態に移行する確率がラベル付けされ、同じ情報が時刻nから時刻n + 1 への遷移行列によって表されます。ただし、マルコフ連鎖は時間的に均一であると想定されることが多く (以下のバリエーションを参照)、その場合、グラフと行列はn とは独立しているため、シーケンスとして表されません。 ${\displaystyle \Pr(X_{n+1}=x\mid X_{n}=x_{n}).}$

これらの説明は、初期分布に依存しないマルコフ連鎖の構造を強調しています。時間的に均一な場合、連鎖は各頂点または状態から隣接する頂点または状態へのホッピングの確率を割り当てる状態マシンとして解釈できます。マシンの状態の確率は、状態空間の要素を入力とするマシンの統計的動作として、または状態の初期分布を入力とするマシンの動作として分析できます。ここで、はアイバーソン括弧です。^{[引用が必要]}${\displaystyle \Pr(X_{1}=x_{1}).}$${\displaystyle \Pr(X_{n}=x\mid X_{1}=x_{1})}$${\displaystyle x_{1}}$${\displaystyle \Pr(X_{1}=y)=[x_{1}=y]}$${\displaystyle [P]}$

• 時間均質マルコフ連鎖（または定常マルコフ連鎖）は、

${\displaystyle \Pr(X_{n+1}=x\mid X_{n}=y)=\Pr(X_{n}=x\mid X_{n-1}=y)}$

遷移の確率はnに依存しない。[ 1 ^]

• 記憶を持つマルコフ連鎖（またはm次マルコフ連鎖）

ここでmは有限であり、

${\displaystyle {\begin{aligned}&\Pr(X_{n}=x_{n}\mid X_{n-1}=x_{n-1},X_{n-2}=x_{n-2},\dots ,X_{1}=x_{1})\\={}&\Pr(X_{n}=x_{n}\mid X_{n-1}=x_{n-1},X_{n-2}=x_{n-2},\dots ,X_{nm}=x_{nm}){\text{ }}n>m の場合\end{aligned}}}$

言い換えれば、将来の状態は過去のm個の状態に依存します。状態空間として順序付けられたm個のX値の組をとることによって、「古典的な」マルコフ特性を持つ連鎖を構築することができます。つまり、。^[要出典]${\displaystyle (Y_{n})}$${\displaystyle (X_{n})}$${\displaystyle Y_{n}=\left(X_{n},X_{n-1},\ldots ,X_{n-m+1}\right)}$

n時間ステップ で状態iから状態jに移行する確率は

${\displaystyle p_{ij}^{(n)}=\Pr(X_{n}=j\mid X_{0}=i)}$

そして、単一ステップの遷移は

${\displaystyle p_{ij}=\Pr(X_{1}=j\mid X_{0}=i).}$

時間同次マルコフ連鎖の場合:

${\displaystyle p_{ij}^{(n)}=\Pr(X_{k+n}=j\mid X_{k}=i)}$

そして

${\displaystyle p_{ij}=\Pr(X_{k+1}=j\mid X_{k}=i).}$

n段階の遷移確率はチャップマン・コルモゴロフ方程式を満たし、 0 <  k  <  nとなる任意のkに対して、

${\displaystyle p_{ij}^{(n)}=\sum _{r\in S}p_{ir}^{(k)}p_{rj}^{(nk)}}$

ここでSはマルコフ連鎖の状態空間である。^[1]

限界分布Pr( X _n  =  x )は、時刻nにおける状態の分布です。初期分布はPr( X ₀  =  x )です。1つの時間ステップにおけるプロセスの進化は次のように記述されます。

${\displaystyle \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）は指数ではなくインデックスです）。

状態jが状態iからアクセス可能である（i  →  jと表記）とは、状態iで開始されたシステムが、ある時点で状態jに遷移する確率がゼロではない場合をいう。形式的には、状態j が状態iからアクセス可能であるとは、次の整数n _ij  ≥ 0 が存在し、

${\displaystyle \Pr(X_{n_{ij}}=j\mid X_{0}=i)=p_{ij}^{(n_{ij})}>0.}$

状態i は、 i  →  jかつj  →  i の両方のとき、状態jと通信している（i  ↔  jと表記）と言われる。通信クラスとは、 C内のすべての状態ペアが互いに通信するような状態Cの最大の集合である。通信は同値関係であり、通信クラスはこの関係の同値クラスである。^[1]

通信クラスが閉じているのは、そのクラスから出る確率がゼロの場合、つまりiがCにあるがjは C にない場合、iからjにアクセスできない ときです。^[1]通信クラスの集合は、元の状態空間から矢印を継承することで、有向非巡回グラフを形成します。通信クラスが閉じているのは、このグラフに外向きの矢印がない場合のみです。

状態i は、 i  →  jとなるすべてのjに対してj  →  iも真である場合に、本質的または最終的であるといわれます。状態i は、本質的でない場合、非本質的です。^[2]状態が最終的であるのは、その通信クラスが閉じている場合のみです。

マルコフ連鎖は、その状態空間が単一の通信クラスである場合、つまり、任意の状態から任意の状態に到達できる場合、既約であると言われる。^{[1] [3] : 20}

状態が周期を持つとは、状態に戻るのに必ず時間ステップの倍数が発生することを意味する。正式には、状態の周期は次のように定義される。 ${\displaystyle i}$${\displaystyle k}$${\displaystyle i}$${\displaystyle k}$${\displaystyle i}$

${\displaystyle k=\gcd\{n>0:\Pr(X_{n}=i\mid X_{0}=i)>0\}}$

(ここでは最大公約数)ですが、この集合は空でない場合に限られます。それ以外の場合、周期は定義されません。^[1]状態の周期が であっても、段階的に状態に到達できない場合があります。たとえば、時間ステップで状態に戻ることができるとします。は になりますが、 はこのリストに表示されません。 ${\displaystyle \gcd}$${\displaystyle k}$${\displaystyle k}$${\displaystyle \{6,~8,~10,~12,\dots \}}$${\displaystyle k}$${\displaystyle 2}$${\displaystyle 2}$

の場合、状態は非周期的であると言われます。それ以外の場合 ( )、状態は周期 で周期的であると言われます 。周期性はクラスのプロパティです。つまり、状態に周期がある場合、その通信クラスのすべての状態には周期 があります。^[1]${\displaystyle k=1}$${\displaystyle k>1}$${\displaystyle k}$${\displaystyle k}$${\displaystyle k}$

状態i が一時的であるとは、状態iから開始した場合、 iに戻らない確率がゼロではない場合を指します。正式には、ランダム変数 T _{i を}状態iへの最初の復帰時間(「ヒット時間」) とします。

${\displaystyle T_{i}=\inf\{n\geq 1:X_{n}=i\}.}$

番号

${\displaystyle f_{ii}^{(n)}=\Pr(T_{i}=n\mid X_{0}=i)}$

は、 nステップ後に初めて状態iに戻る確率である。したがって、状態iが過渡的であるのは、

${\displaystyle \Pr(T_{i}<\infty \mid X_{0}=i)=\sum _{n=1}^{\infty }f_{ii}^{(n)}<1.}$

状態iは、一時的でない場合は再帰的（または持続的）である。再帰性と一時性はクラスの特性であり、つまり、通信するクラスのすべてのメンバーに対して等しく当てはまるか当てはまらないかのどちらかである。^[1]

状態iが再帰的であるためには、iへの訪問回数の期待値が無限大である必要がある: ^[1]

${\displaystyle \sum _{n=0}^{\infty }p_{ii}^{(n)}=\infty .}$

たとえ確率 1 でヒット時間が有限であったとしても、期待値が有限である必要はありません。状態iでの平均再発時間は期待される復帰時間M _iです。

${\displaystyle M_{i}=E[T_{i}]=\sum _{n=1}^{\infty }n\cdot f_{ii}^{(n)}.}$

M _iが有限の場合、状態i は正再帰（または非ヌル永続）です。それ以外の場合、状態iはヌル再帰（またはヌル永続）です。正再帰とヌル再帰はクラスのプロパティです。^[1]

状態iは、この状態から抜け出すことが不可能な場合、吸収的であると言われる。したがって、状態iが吸収的であるのは、

${\displaystyle p_{ii}=1{\text{ and }}p_{ij}=0{\text{ for }}i\not =j.}$

あらゆる状態が吸収状態に到達できる場合、マルコフ連鎖は吸収マルコフ連鎖である。^{[4] [5]}

マルコフ連鎖は、その状態に対して 確率分布πが存在し、

${\displaystyle \pi _{i}\Pr(X_{n+1}=j\mid X_{n}=i)=\pi _{j}\Pr(X_{n+1}=i\mid X_{n}=j)}$

すべての時刻nとすべての状態iおよびjに対して、この条件は詳細バランス条件 (またはローカルバランス方程式) として知られています。

固定された任意の時間nを考慮し、略記法を用いると

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

詳細なバランス方程式は次のように簡潔に書くことができる。

${\displaystyle \pi _{i}p_{ij}=\pi _{j}p_{ji}\,.}$^[1]

nからn + 1までの単一のタイムステップは、 各人iが最初にπ _iドルを持っていて、各人jにその一部p _ijを支払うと考えることができる。詳細なバランス条件は、各支払いで、他の人が正確に同じ金額を返済することを規定している。^[6]明らかに、各人が持っているお金の合計額πは、タイムステップ後も同じままです。なぜなら、支出されたすべてのドルは、対応する受け取ったドルとバランスが取れているからです。これは、より正式には、次の等式で示すことができます。

${\displaystyle \sum _{i}\pi _{i}p_{ij}=\sum _{i}\pi _{j}p_{ji}=\pi _{j}\sum _{i}p_{ji}=\pi _{j}\,,}$

これは本質的に、時間ステップ中に人j が受け取るお金の合計額 (自分自身からのものも含む) は、彼が他の人に支払うお金の額に等しいことを示しています。これは、すべてのお金が使われると仮定されているため (つまり、 p _{ji の}合計はi分の 1 になる)、彼が最初に持っていたすべてのお金に等しくなります。この仮定は技術的なもので、実際に使われなかったお金は単に人jから彼自身に支払われると考えられるためです (つまり、p _jjは必ずしもゼロではありません)。

n は任意であるため、この推論は任意のnに対して成り立ち、したがって可逆マルコフ連鎖ではπ は常にすべてのnに対して Pr( X _{n +1}  =  j  |  X _n  =  i ) の定常分布になります。

マルコフ連鎖が定常分布から始まる場合、つまり の場合、すべてのおよびに対して、詳細なバランス方程式は次のように表すことができます。 ${\displaystyle \Pr(X_{0}=i)=\pi _{i}}$${\displaystyle \Pr(X_{n}=i)=\pi _{i}}$${\displaystyle n}$

${\displaystyle \Pr(X_{n}=i,X_{n+1}=j)=\Pr(X_{n+1}=i,X_{n}=j)\,.}$

この最後の式の左辺と右辺は、時間インデックスnと n  + 1 が逆になっていることを除いて同一です。

コルモゴロフの基準は、遷移行列の確率から直接、マルコフ連鎖が可逆的であるための必要かつ十分な条件を与えます。この基準では、すべての閉じたループの周りの確率の積が、ループの周りの両方向で同じであることが要求されます。

可逆マルコフ連鎖は、マルコフ連鎖モンテカルロ (MCMC) アプローチでよく使用されます。これは、目的の分布πの詳細なバランス方程式は、必然的に、 π が定常分布となるようにマルコフ連鎖が構築されていることを意味するためです。複数の遷移行列が使用される時間不均一マルコフ連鎖の場合でも、各遷移行列が目的のπ分布と詳細なバランスを示す場合、必然的に、 πがマルコフ連鎖の定常分布であること を意味します。

遷移行列、スカラー積によって誘導される任意のノルム、および任意の確率ベクトルによって与えられる任意の時間同次マルコフ連鎖に対して、に従って可逆で、ノルムに従って に最も近い唯一の遷移行列が存在する。この行列は、2次凸最適化問題を解くことによって計算できる。^[7]${\displaystyle P\in \mathbb {R} ^{n\times n}}$${\displaystyle ||\cdot ||}$${\displaystyle \mathbb {R} ^{n\times n}}$${\displaystyle \pi }$${\displaystyle P^{*}}$${\displaystyle \pi }$${\displaystyle P}$${\displaystyle ||\cdot ||.}$${\displaystyle P^{*}}$

たとえば、次のマルコフ連鎖を考えてみましょう。

このマルコフ連鎖は可逆ではない。フロベニウスノルムによれば、最も近い可逆マルコフ連鎖は次のように計算できる。 ${\displaystyle \pi =\left({\frac {1}{3}},{\frac {1}{3}},{\frac {1}{3}}\right)}$

確率ベクトルをランダムに選ぶと、フロベニウスノルムに従った最も近い可逆マルコフ連鎖は、近似的に次のように与えられる。 ${\displaystyle \pi =\left({\frac {1}{4}},{\frac {1}{4}},{\frac {1}{2}}\right)}$

分布は確率行列を持つマルコフ連鎖の定常分布であるためには、次のように書くことができる。^[1]${\displaystyle \pi }$${\displaystyle P}$${\displaystyle \pi P=\pi }$

${\displaystyle \forall j\in \mathbb {S} :\sum _{i\in \mathbb {S} }\pi _{i}p_{ij}=\pi _{j}}$。

この条件は、 を意味し、したがって、マルコフ連鎖が初期分布を持つ場合、任意の に対して （分布において） となる。^[1]${\displaystyle \pi P^{n}=\pi }$${\displaystyle (X_{n},n\in \mathbb {N} )}$${\displaystyle X_{0}=\pi }$${\displaystyle X_{n}=\pi }$${\displaystyle n\in \mathbb {N} }$

マルコフ連鎖が既約である場合、それが定常分布を持つのは、それが正の再帰的である場合のみである。^[8]この場合、そのような分布の唯一のものは、 iの平均再帰時間によって与えられる。^[1]${\displaystyle \pi _{i}={\frac {1}{M_{i}}}}$${\displaystyle M_{i}=\mathbb {E} (T_{i})}$

チェーンに複数の閉じた通信クラスがある場合、その定常分布は一意ではありません (チェーン内の任意の閉じた通信クラスについて考えます。それぞれが独自の一意の定常分布を持ちます。これらの分布をチェーン全体に拡張し、通信クラスの外側のすべての値をゼロに設定すると、元のチェーンの不変測度の集合はのすべての凸結合の集合になります)。ただし、状態jが非周期的である場合、 および他の任意の状態iについて、チェーンがiで開始した場合に 状態jを訪れる確率をf _ijとします。 ${\displaystyle C_{i}}$${\displaystyle \pi _{i}}$${\displaystyle \pi _{i}}$${\displaystyle \lim \nolimits _{n\rightarrow \infty }p_{jj}^{(n)}={\tfrac {C}{M_{j}}}}$${\displaystyle \lim \nolimits _{n\rightarrow \infty }p_{ij}^{(n)}=C{\tfrac {f_{ij}}{M_{j}}}.}$

状態iが周期k  > 1 で周期的である場合、限界は 存在しませんが、すべての整数rに対して 限界は 存在します 。 ${\displaystyle \lim \nolimits _{n\rightarrow \infty }p_{ii}^{(n)}}$${\displaystyle \lim \nolimits _{n\rightarrow \infty }p_{ii}^{(kn+r)}}$

マルコフ連鎖は、均衡分布を持つために必ずしも時間的に同次である必要はない。状態 に対する確率分布が${\displaystyle {\boldsymbol {\pi }}}$

${\displaystyle \pi _{j}=\sum _{i\in S}\pi _{i}\,\Pr(X_{n+1}=j\mid X_{n}=i)}$

すべての状態jとすべての時刻nに対して、はマルコフ連鎖の平衡分布です。これは、複数の異なる遷移行列が使用される状況でマルコフ連鎖モンテカルロ (MCMC) 法で発生する可能性があります。これは、各行列が特定の種類の混合に対して効率的である一方で、各行列が共有の平衡分布を尊重するためです。 ${\displaystyle {\boldsymbol {\pi }}}$

ヒット時間とは、与えられた一連の状態から始まり、連鎖が与えられた状態または一連の状態に到達するまでの時間です。このような時間間隔の分布は、位相型分布を持ちます。最も単純な分布は、単一の指数分布遷移の分布です。^[要出典]

状態A  ⊆  Sのサブセットに対して、ヒット回数のベクトルk ^A（要素は、状態iから始まって、チェーンがセットA内のいずれかの状態に入る期待値を表す）は、 ^[9]の最小の非負解である。${\displaystyle k_{i}^{A}}$

${\displaystyle {\begin{aligned}k_{i}^{A}=0&{\text{ for }}i\in A\\-\sum _{j\in S}q_{ij}k_{j}^{A}=1&{\text{ for }}i\notin A.\end{aligned}}}$

エルゴード理論の一例として、エルゴード定理は、既約な非周期マルコフ連鎖において、任意の2つの状態iとjに対して、^[1]

${\displaystyle p_{i,j}^{(n)}\rightarrow {\frac {1}{M_{j}}}}$として。${\displaystyle n\rightarrow \infty }$