吸収マルコフ連鎖

数学の確率理論では、吸収マルコフ連鎖とは、あらゆる状態が吸収状態に到達できるマルコフ連鎖のことです。吸収状態とは、一度入ったら抜け出せない状態です。

一般的なマルコフ連鎖と同様に、無限の状態空間を持つ連続時間吸収マルコフ連鎖が存在する可能性があります。ただし、この記事では離散時間離散状態空間の場合に焦点を当てます。

マルコフ連鎖は吸収連鎖である^{[1] [2]}

1. 少なくとも1つの吸収状態があり、
2. 有限数のステップで、任意の状態から少なくとも 1 つの吸収状態に移行することが可能です。

吸収マルコフ連鎖では、吸収していない状態は一時的と呼ばれます。

遷移行列Pを持つ吸収マルコフ連鎖にt個の遷移状態とr個の吸収状態があるとする。一般的な遷移行列とは異なり、 Pの行はソースを表し、列は宛先を表す。

${\displaystyle P={\begin{bmatrix}Q&R\\\mathbf {0} &I_{r}\end{bmatrix}},}$

ここで、Qはt行t列の行列、Rは非ゼロのt行r列の行列、0はr行t 列のゼロ行列、I _{r は}r行r列の 単位行列です。したがって、Q はある過渡状態から別の過渡状態への遷移の確率を表し、R はある過渡状態からある吸収状態への遷移の確率を表します。

iからjへ正確にkステップで遷移する確率はP ^{kの (} i , j ) エントリであり、以下でさらに計算されます。過渡状態のみを考慮する場合、確率はP ^kの左上、 Q ^kの( i , j ) エントリにあります。

吸収マルコフ連鎖の基本的な性質は、吸収される前の過渡状態iから過渡状態jへの訪問回数の期待値である。これは、すべてのk (0 から ∞ まで) についてQ ^{k を}合計して得られる、いわゆる基本行列Nの ( i ,  j ) 要素によって与えられることが証明できる。

${\displaystyle N:=\sum _{k=0}^{\infty }Q^{k}=(I_{t}-Q)^{-1},}$

ここで、I _{t は}t行t列の単位行列です。この式の計算は、スカラーの等比級数と同等の行列です。 ${\displaystyle {\textstyle \sum }_{k=0}^{\infty }q^{k}={\tfrac {1}{1-q}}}$

行列Nがわかれば、マルコフ連鎖の他の特性も簡単に得られる。^[2]

過渡状態iから開始して、吸収状態に吸収されるまでの予想されるステップ数は、過渡状態の合計によって計算できます。値はベクトルの i番目のエントリによって与えられます。

${\displaystyle \mathbf {t} :=N\mathbf {1} ,}$

ここで、1 は要素がすべて 1 である 長さt の列ベクトルです。

帰納的に、

${\displaystyle P^{k}={\begin{bmatrix}Q^{k}&(I_{t}-Q^{k})NR\\\mathbf {0} &I_{r}\end{bmatrix}}.}$

遷移状態iから開始して最終的に吸収状態jに吸収される確率は、行列の ( i , j )要素によって与えられる。

${\displaystyle B:=NR}$。

この行列の列数は吸収状態rの数に等しくなります。

これらの確率の近似値は、十分大きなkの値（ i は過渡状態のインデックス、j は吸収状態のインデックス ）に対する の（ i , j）項から直接得ることもできる。これは、${\displaystyle P^{k}}$

${\displaystyle \left(\lim _{k\to \infty }P^{k}\right)_{i,t+j}=B_{i,j}}$。

過渡状態iから開始したときに過渡状態jを訪れる確率は、行列の ( i , j )要素である。

${\displaystyle H:=(N-I_{t})(N_{\operatorname {dg} })^{-1},}$

ここで、N _{dg は}Nと同じ対角を持つ対角行列です。

遷移状態i（吸収される前）から遷移状態jへの訪問回数の分散は、行列の （ i、j ）要素である。

${\displaystyle N_{2}:=N(2N_{\operatorname {dg} }-I_{t})-N_{\operatorname {sq} },}$

ここで、N _{sq は}Nとそれ自身とのアダマール積です(つまり、 Nの各要素が2 乗されます)。

過渡状態iから開始したときに吸収される前のステップ数の分散は、ベクトルの i番目のエントリです。

${\displaystyle (2N-I_{t})\mathbf {t} -\mathbf {t} _{\operatorname {sq} },}$

ここで、t _{sq は}tとそれ自身とのアダマール積です（つまり、 N _sqと同様に、 tの各要素は2 乗されます）。

公平なコインを繰り返し投げて、表、裏、表の順番が出るまで繰り返し投げるプロセスを考えてみましょう。このプロセスは、遷移行列を持つ吸収マルコフ連鎖によってモデル化されます。

${\displaystyle P={\begin{bmatrix}1/2&1/2&0&0\\0&1/2&1/2&0\\1/2&0&0&1/2\\0&0&0&1\end{bmatrix}}.}$

最初の状態は空の文字列、2 番目の状態は文字列 "H"、3 番目の状態は文字列 "HT"、4 番目の状態は文字列 "HTH" を表します。実際には、文字列 "HTH" が生成されるとコイン投げは停止しますが、吸収マルコフ連鎖の観点では、プロセスは文字列 "HTH" を表す吸収状態に移行しているため、そこから抜け出すことはできません。

この吸収マルコフ連鎖の基本行列は

${\displaystyle {\begin{aligned}N&=(IQ)^{-1}=\left({\begin{bmatrix}1&0&0\\0&1&0\\0&0&1\end{bmatrix}}-{\begin{bmatrix}1/2&1/2&0\\0&1/2&1/2\\1/2&0&0\end{bmatrix}}\right)^{-1}\\[4pt]&={\begin{bmatrix}1/2&-1/2&0\\0&1/2&-1/2\\-1/2&0&1\end{bmatrix}}^{-1}={\begin{bmatrix}4&4&2\\2&4&2\\2&2&2\end{bmatrix}}.\end{aligned}}}$

各過渡状態から始まるステップの期待値は

${\displaystyle \mathbf {t} =N\mathbf {1} ={\begin{bmatrix}4&4&2\\2&4&2\\2&2&2\end{bmatrix}}{\begin{bmatrix}1\\1\\1\end{bmatrix}}={\begin{bmatrix}10\\8\\6\end{bmatrix}}.}$

したがって、シーケンス (表、裏、表) が観察されるまでのコイン投げの予想回数は 10 であり、状態のエントリは空の文字列を表します。

完全に偶然に基づくゲームは、吸収マルコフ連鎖によってモデル化できます。この典型的な例は、古代インドのボードゲーム「蛇と梯子」です。左のグラフ^[3]は、遷移行列がどんどん大きくなるにつれて、最後の正方形を表す唯一の吸収状態の確率質量をプロットしています。ゲームを完了するための予想されるターン数を決定するには、上記のようにベクトルtを計算し、約 39.2 である t _{startを調べます。}

血液製品や診療所での感染症検査は、吸収マルコフ連鎖の例としてよく教えられています。^[4]例えば、米国疾病予防管理センター（CDC）のHIVとB型肝炎の公開モデル^[5]は、吸収マルコフ連鎖が病気の検出につながる可能性があるのに対し、他の手段では検出が失敗するという特性を示しています。

標準的な CDC モデルでは、マルコフ連鎖には 5 つの状態があります。個人が感染していない状態、感染しているがウイルスが検出されない状態、ウイルスが検出される状態、クリニックから離脱/消失した状態、または検出された状態 (目標) です。マルコフ状態間の遷移の一般的な速度は、単位時間あたりのウイルス感染の確率p 、ウィンドウ期間の除去率w (ウイルスが検出可能になるまでの時間)、システムからの離脱/消失率q 、検出率d です(医療システムが血液製品または問題の患者の検査を実施する 一般的な速度を想定)。${\displaystyle \lambda}$

したがって、次のようにモデルの各次の状態への移行確率を掛け合わせることで、マルコフ モデルに沿って「歩き」、検出されない状態から始まる人物の全体的な検出確率を特定することができます。

${\displaystyle {\frac {p}{(p+q)}}{\frac {w}{(w+q)}}{\frac {d}{(d+q)}}}$。

CDC の主な懸念事項である偽陰性検査の絶対数の合計は、検査率に、感染しているが検出できない状態に達する確率を掛け、感染しているが検出できない状態が続く期間を掛け合わせたものになります。

${\displaystyle {\frac {p}{(p+q)}}{\frac {1}{(w+q)}}\lambda }$。

• 離散位相型分布
• 吸収集合（ランダム力学系）

• Wolfram デモンストレーション プロジェクト: 吸収マルコフ連鎖
• マルコフ連鎖としての独占