Aritalab:Lecture/NetworkBiology/Markov Chains
m |
m (→定常分布をもつ条件) |
||
(24 intermediate revisions by one user not shown) | |||
Line 6: | Line 6: | ||
離散確率過程<math>X_0, X_1, X_2 \ldots</math>は | 離散確率過程<math>X_0, X_1, X_2 \ldots</math>は | ||
− | <math>\mbox{ | + | <math>\mbox{Prob}(X_t = a_t | X_{t-1} = a_{t-1}, X_{t-2} = a_{t-2}, \ldots X_0 = a_0 ) |
− | = \mbox{ | + | = \mbox{Prob}(X_t = a_t | X_{t-1} = a_{t-1}) |
</math> | </math> | ||
を満たすときにマルコフ連鎖 (Markov chain) と呼ばれます。マルコフとはロシアの統計学者 Andrei A. Markov (1856-1922) のことで、マルコフ連鎖に関する多くの功績を残しました。状態 (state) <math>X_t</math> が状態 <math>X_{t-1}</math> のみに依存して決まる性質をマルコフ性 (Markov property) または無記憶性 (memoryless property) といいます。 | を満たすときにマルコフ連鎖 (Markov chain) と呼ばれます。マルコフとはロシアの統計学者 Andrei A. Markov (1856-1922) のことで、マルコフ連鎖に関する多くの功績を残しました。状態 (state) <math>X_t</math> が状態 <math>X_{t-1}</math> のみに依存して決まる性質をマルコフ性 (Markov property) または無記憶性 (memoryless property) といいます。 | ||
− | マルコフ連鎖において状態 ''i'' から ''j'' への遷移確率を<math>p_{ | + | マルコフ連鎖において状態 ''i'' から ''j'' への遷移確率を<math>p_{ij} = \mbox{Pr}(X_t = j | X_{t-1} = i )</math> と書けば、マルコフ連鎖は遷移行列 |
<math> | <math> | ||
{\mathbf P} = | {\mathbf P} = | ||
\begin{bmatrix} | \begin{bmatrix} | ||
− | p_{ | + | p_{11} & p_{12} & \cdots & p_{1j} & \cdots \\ |
− | p_{ | + | p_{21} & p_{22} & \cdots & p_{2j} & \cdots \\ |
\vdots & \vdots & \ddots & \vdots & \ddots \\ | \vdots & \vdots & \ddots & \vdots & \ddots \\ | ||
− | p_{ | + | p_{i1} & p_{i2} & \cdots & p_{ij} & \cdots \\ |
\vdots & \vdots & \ddots & \vdots & \ddots \\ | \vdots & \vdots & \ddots & \vdots & \ddots \\ | ||
\end{bmatrix} | \end{bmatrix} | ||
</math> | </math> | ||
− | で記述できます。<ref>状態 i から j への遷移確率を p<sub> | + | で記述できます。<ref>状態 i から j への遷移確率を p<sub>ij</sub> とする記法が主流ですが (Karlin & Taylor 1975)、Linda JS Allen (2011 2nd Ed) では j から i への遷移確率を p<sub>ij</sub> と定義しています。そうすると定常分布を考える際に 以下で書くように行ベクトル π を用いて <math>\bar\pi = \bar\pi \mathbf P</math> とするのではなく、列ベクトルを用いて <math>\bar\pi = \mathbf P \bar\pi </math> と書けるようになります。記法上の問題であり、本質はかわりません。</ref> |
遷移確率を表すので行列の行方向に足し合わせた値は必ず 1 になっており、確率行列 (stochastic matrix) と呼ばれます。もし行方向に足し合わせても 1 になる場合、二重確率行列 (doubly stochastic matrix) と呼ばれます。 | 遷移確率を表すので行列の行方向に足し合わせた値は必ず 1 になっており、確率行列 (stochastic matrix) と呼ばれます。もし行方向に足し合わせても 1 になる場合、二重確率行列 (doubly stochastic matrix) と呼ばれます。 | ||
記法を拡張し、''i'' から ''j'' へ正確に ''m'' ステップで移る遷移確率を | 記法を拡張し、''i'' から ''j'' へ正確に ''m'' ステップで移る遷移確率を | ||
− | <math>p_{ | + | <math>p_{ij}^{(m)} = \mbox{Prob}(X_{t+m} = j | X_{t} = i )</math> |
− | + | と書きましょう。右肩にある (m) という表記は、m ステップ後という意味で m 乗ではありません。1ステップ目で移動した先を ''k'' と書くと | |
− | <math>\textstyle p_{ | + | <math>\textstyle p_{ij}^{(m)} = \sum_{k} p_{ik} \cdot p^{(m-1)}_{kj} </math> |
であるから、遷移行列<math>{\mathbf P}</math>を ''m'' 乗すれば正確に ''m'' ステップで移った先を示す遷移行列を得ます(数学的帰納法)。また記法をそろえるために | であるから、遷移行列<math>{\mathbf P}</math>を ''m'' 乗すれば正確に ''m'' ステップで移った先を示す遷移行列を得ます(数学的帰納法)。また記法をそろえるために | ||
− | <math>p_{ | + | <math>p_{ij}^{(1)} = p_{ij}</math> |
− | <math>p_{ | + | <math>p_{ij}^{(0)} = |
\begin{cases}\textstyle | \begin{cases}\textstyle | ||
1 & (j = i)\\ | 1 & (j = i)\\ | ||
0 & (j \not= i) | 0 & (j \not= i) | ||
− | \end{cases}</math> と定義します。 | + | \end{cases}</math> |
+ | |||
+ | と定義します。 | ||
===チャップマン-コルモゴロフの等式=== | ===チャップマン-コルモゴロフの等式=== | ||
− | ''m'' ステップの遷移を、 ''s'' ステップと ''m'' − ''s'' ステップに分解する以下の式は、チャップマン- | + | ''m'' ステップの遷移を、 ''s'' ステップと ''m'' − ''s'' ステップに分解する以下の式は、チャップマン-コルモゴロフの等式と呼ばれます<ref> |
− | + | ;チャップマン-コルモゴロフの等式の証明 | |
− | < | + | |
− | + | ||
− | ; | + | |
<math> | <math> | ||
\begin{align} | \begin{align} | ||
− | p^ | + | p^{(m)}_{ij} & = \mbox{Prob}\{X_m = j | X_0 = i \} \\ |
& = \textstyle\sum^{\infty}_{k=1} \mbox{Prob}\{ X_m = j, X_s = k | X_0 = i \} \\ | & = \textstyle\sum^{\infty}_{k=1} \mbox{Prob}\{ X_m = j, X_s = k | X_0 = i \} \\ | ||
− | |||
& = \textstyle\sum^{\infty}_{k=1} \mbox{Prob}\{ X_m = j | X_s = k, X_0 = i \} \mbox{Prob}\{ X_s = k | X_0 = i \}\\ | & = \textstyle\sum^{\infty}_{k=1} \mbox{Prob}\{ X_m = j | X_s = k, X_0 = i \} \mbox{Prob}\{ X_s = k | X_0 = i \}\\ | ||
& = \textstyle\sum^{\infty}_{k=1} \mbox{Prob}\{ X_m = j | X_s = k \} \mbox{Prob}\{ X_s = k | X_0 = i \} \\ | & = \textstyle\sum^{\infty}_{k=1} \mbox{Prob}\{ X_m = j | X_s = k \} \mbox{Prob}\{ X_s = k | X_0 = i \} \\ | ||
− | & = \textstyle\sum^{\infty}_{k=1} p^{m-s}_{kj} p^ | + | & = \textstyle\sum^{\infty}_{k=1} p^{(m-s)}_{kj} p^{(s)}_{ik} |
\end{align} | \end{align} | ||
− | </math> | + | </math></ref>。 |
− | + | <math>p^{(m)}_{ij} = \textstyle\sum^{\infty}_{k=1} p^{(s)}_{ik} p^{(m-s)}_{kj} \quad (0 < s < m)</math> | |
− | + | ||
+ | 以下でも <math>p^{(m)}_{ij} \geq p^{(s)}_{ik} p^{(m-s)}_{kj} </math> という式をよく使います。 | ||
==既約== | ==既約== | ||
状態 ''i'' から ''j'' へ何ステップかで到達できる場合、''j'' は ''i'' から到達可能 (accessible) と呼びます。 | 状態 ''i'' から ''j'' へ何ステップかで到達できる場合、''j'' は ''i'' から到達可能 (accessible) と呼びます。 | ||
− | 互いに到達可能な状態 ''i, j'' どうしを連結 (communicate) しているといい、<math>i \leftrightarrow j</math> | + | 互いに到達可能な状態 ''i, j'' どうしを連結 (communicate) しているといい、<math>i \leftrightarrow j</math>と書きます。連結性により同値類が形成されます。 |
* 反射律 (reflexivity): いかなる状態 ''i'' も、<math>i \leftrightarrow i</math> | * 反射律 (reflexivity): いかなる状態 ''i'' も、<math>i \leftrightarrow i</math> | ||
Line 76: | Line 75: | ||
また、状態集合 C は、C に属すどの状態からも C 以外の状態に抜け出せないとき、閉じている (closed) といいます。例えば、グラフ表現した際に外に出る辺をもたない状態だけからなる集合は閉じています。 | また、状態集合 C は、C に属すどの状態からも C 以外の状態に抜け出せないとき、閉じている (closed) といいます。例えば、グラフ表現した際に外に出る辺をもたない状態だけからなる集合は閉じています。 | ||
− | ;例: | + | ;例: 1次元のウォーク |
− | 0 と N | + | 0 と N の間を左右に1ステップずつ移動し、0, N を吸収状態とするランダムウォークを考えます。0 から N までの状態は 3 つの同値類 {0}, {1, 2, ..., N−1}, {N} に分かれ、{0, N} は閉じています。 |
− | + | ||
==周期性== | ==周期性== | ||
状態 ''i'' に戻ってくるまでのステップ数が自然数 ''k'' (>1) の倍数回に限られ、しかも ''k'' がこの性質を持つ最大公約数の場合、状態 ''i'' は周期 ''k'' でといいます。 | 状態 ''i'' に戻ってくるまでのステップ数が自然数 ''k'' (>1) の倍数回に限られ、しかも ''k'' がこの性質を持つ最大公約数の場合、状態 ''i'' は周期 ''k'' でといいます。 | ||
''k'' = 1 のとき、状態は非周期的であるといいます。マルコフ連鎖の中で同じ同値類に属する (communicativeな) 状態 i, j は同じ周期をもちます<ref> | ''k'' = 1 のとき、状態は非周期的であるといいます。マルコフ連鎖の中で同じ同値類に属する (communicativeな) 状態 i, j は同じ周期をもちます<ref> | ||
− | ; | + | ;同じ同値類に属する状態の周期が等しいことの証明 |
周期が 0 のときは自明。状態 i の周期が d(i) ≥ 1 と仮定します。状態 i から s ステップで i に戻る確率が 0 より大きくなる場合 <math>(p^{(s)}_{ii} > 0)</math> 、d(i) は s を割り切ります。 i と j が同値類に属する場合、 i → j を m ステップ、 j → i を n ステップで移動することが可能 <math>(p^{(n)}_{ji} > 0, p^{(m)}_{ij} > 0)</math> ですから | 周期が 0 のときは自明。状態 i の周期が d(i) ≥ 1 と仮定します。状態 i から s ステップで i に戻る確率が 0 より大きくなる場合 <math>(p^{(s)}_{ii} > 0)</math> 、d(i) は s を割り切ります。 i と j が同値類に属する場合、 i → j を m ステップ、 j → i を n ステップで移動することが可能 <math>(p^{(n)}_{ji} > 0, p^{(m)}_{ij} > 0)</math> ですから | ||
Line 90: | Line 88: | ||
となります。状態 j の周期は (n + ks + m) をどんな正の整数 k に対しても割り切るので、s も割り切ります。ここから d(j) ≤ d(i) が導かれます。同様の議論で d(i) ≤ d(j) も成り立つので d(i) = d(j) となります。 | となります。状態 j の周期は (n + ks + m) をどんな正の整数 k に対しても割り切るので、s も割り切ります。ここから d(j) ≤ d(i) が導かれます。同様の議論で d(i) ≤ d(j) も成り立つので d(i) = d(j) となります。 | ||
</ref>。 | </ref>。 | ||
− | ; | + | ;例:円周上のウォーク |
− | N | + | 円周上に配置された N 状態が一方向につながったマルコフ連鎖は、規約で周期 N を持ちます。遷移行列 '''P''' を N 乗すると、恒等行列 '''I''' になります。 |
+ | ;例: 1次元のウォーク | ||
+ | 原点からスタートして左右に1ステップずつ移動するウォークでは、原点に戻るまでのステップ数が必ず偶数です。つまり、状態 0 は周期 2 になります。いずれの状態も周期は 2 です。 | ||
==再帰性== | ==再帰性== | ||
− | 状態 ''i'' から出発し時刻 ''t'' になって初めて ''j'' に到達する確率を<math>f^{(t)}_{ | + | 状態 ''i'' から出発し時刻 ''t'' になって初めて ''j'' に到達する確率を<math>f^{(t)}_{ij}</math>と書くことにします。 |
− | 前出の<math>p^{(t)}_{ | + | 前出の<math>p^{(t)}_{ij}</math>は複数回 ''j'' を訪れることを許すため、<math>f^{(t)}_{ij} \leq p^{(t)}_{ij}</math>となります。 |
− | 同じ状態に初めて戻る確率 <math>f^{(t)}_{ | + | ===再帰時間=== |
− | : <math>\textstyle \sum_{t= 1}^{\infty} | + | 同じ状態に初めて戻る確率 <math>f^{(t)}_{ii}</math> を初再帰確率 (first return probability) と呼び<math>f^{(0)}_{ii} = 0</math> と定義します。状態 ''i'' は |
− | : <math>\textstyle \sum_{t= 1}^{\infty} | + | : <math>\textstyle \sum_{t=1}^{\infty} f^{(t)}_{ii} < 1</math>であれば再帰不確実 (transient) |
− | + | : <math>\textstyle \sum_{t=1}^{\infty} f^{(t)}_{ii} = 1</math>であれば再帰確実 (recurrent) | |
+ | と呼びます。全ての状態が再帰確実であれば、マルコフ連鎖自体を再帰確実と呼びます。 | ||
− | 状態 ''i'' | + | ===平均初再帰時間 MFRT=== |
− | + | 状態 ''i'' における平均初再帰時間 (mean first return time または mean recurrence time) を | |
− | + | ||
− | <math>\textstyle \ | + | <math>\mu_{ii} = \textstyle\sum^{\infty}_{t=1} tf^{(t)}_{ii}</math> |
− | + | と書きます。状態 ''i'' が再帰不確実な場合は <math>\mu_{ii} = \infty</math> です。 | |
− | + | ||
− | <math>\ | + | 状態 ''i'' が再帰確実でも <math>\mu_{ii}</math> が有限とは限りません。初再帰時間の期待値が有限なとき有限再帰 (positive recurrent)、そうでない場合をゼロ再帰 (null recurrent) と呼びます。ゼロ再帰性を満たすには無限の状態数が必要です。 |
− | + | ;例:2 × 2 行列 | |
− | + | 以下の確率行列を持つ 2 状態のマルコフ連鎖は有限再帰的です。 | |
− | + | ||
− | + | ||
− | + | <math> | |
− | 0 | + | {\mathbf P} = |
+ | \begin{bmatrix} | ||
+ | p_{11} & p_{12} \\ | ||
+ | p_{21} & p_{22} \\ | ||
+ | \end{bmatrix}\quad | ||
+ | 0 < p_{ii} < 1 \ (i = 1,2) | ||
+ | </math> | ||
− | + | 直感的には 2 状態の間を自由に行き来できるため、必ず戻ってきます<ref> | |
− | + | ;例:2 × 2 行列が正再帰的になることの証明 | |
+ | 確率行列は行方向の和が必ず 1 になるため、行列の要素は全て正の値をとります。一般に n ≥ 3 について | ||
− | + | <math>f^{(n)}_{11} = p_{12}p^{n-2}_{22}p_{21} </math> | |
− | + | ||
− | + | が成立します。状態 1 の再帰確率は 1 になります。状態 2 についても同じです。しかし平均初再帰時間は有限になります。 | |
− | + | <math> | |
− | + | \begin{align} | |
+ | \textstyle\sum^{\infty}_{n=1}f^{(n)}_{11} | ||
+ | &= p_{11} + p_{12}p_{21}\textstyle\sum^{\infty}_{n=0}p^{n}_{22}\\ | ||
+ | &= p_{11} + p_{12}p_{21}\textstyle\frac{1}{(1-p_{22})} | ||
+ | = p_{11} + p_{12} = 1\\ | ||
+ | \mu_{11} &= \textstyle\sum^{\infty}_{n=1} n \cdot f^{(n)}_{11} = p_{11} + 2 (p_{12}p_{21}) + 3 (p_{12}p_{22}p_{21}) + 4 (p_{12}p_{22}^2p_{21}) + 5 ...\\ | ||
+ | &= p_{11} + p_{12}p_{21} \textstyle\sum^{\infty}{n=0}(n+2)p_{22}^n\\ | ||
+ | &= p_{11} + p_{12} + p_{12}p_{21} \textstyle\sum^{\infty}{n=0}(n+1)p_{22}^n\\ | ||
+ | &= 1 + p_{12}p_{21}\frac{1}{(1 - p_{22})^2}\\ | ||
+ | &= 1 + \frac{p_{12}}{p_{21}} | ||
+ | \end{align} | ||
+ | </math> | ||
+ | </ref> | ||
+ | 。 | ||
− | + | ;例:ゼロ再帰的なマルコフ連鎖 | |
+ | 正の整数値に対応するマルコフ連鎖を仮定し、状態 i から確率 i/(i + 1) で状態 i + 1 に、確率 1/(i + 1) で状態 1 に移動するとします。 | ||
− | + | <math> | |
− | + | {\mathbf P} = | |
+ | \begin{bmatrix} | ||
+ | 1/2 & 1/2 & 0 & 0 & \cdots \\ | ||
+ | 1/3 & 0 & 2/3 & 0 & \cdots \\ | ||
+ | 1/4 & 0 & 0 & 3/4 & \cdots \\ | ||
+ | 1/5 & 0 & 0 & 0 & \cdots \\ | ||
+ | \vdots & \vdots & \vdots & \vdots | ||
+ | \end{bmatrix} | ||
+ | </math> | ||
− | < | + | 高い確率で無限遠に進んでいけるため、状態 1 に初めて戻るまでの期待値は無限大でゼロ再帰的です<ref> |
− | + | ;ゼロ再帰性の証明 | |
+ | 状態 1 からスタートし最初の ''t'' ステップで 1 に戻らない確率は | ||
− | + | <math>\textstyle \prod^t_{j=1} \frac{j}{j+1} = \frac{1}{t+1} \xrightarrow{t \rightarrow \infty} 0</math> | |
− | + | ||
− | <math>\textstyle | + | したがって状態 1 は再帰確実 <math>\textstyle f^{(t)}_{11} = \frac{1}{t (t + 1)}</math> (''t'' − 1 ステップ 1 に戻らず、''t'' ステップ目で 1 に戻る)。しかし、状態 1 に初めて戻るまでの期待値は無限大なので、ゼロ再帰。 |
− | + | <math>\textstyle \mu_{11} = \sum^{\infty}_{t=1} t \cdot f^{(t)}_{11} = \sum^{\infty}_{t=1} \frac{1}{t+1} \xrightarrow{t \rightarrow \infty} \infty</math> | |
− | + | </ref>。 | |
− | + | ||
− | + | ===通過時間、平均初通過確率 MFPT=== | |
− | + | ||
− | + | 状態 i から始めて j に最初に訪れる確率 <math>f^{(t)}_{ij}</math> を初通過確率 (first passage time probability) と呼び、 <math>f^{(0)}_{ij} = 0</math> と定義します。平均初通過時間 (mean first passage time; MFPT) も同様に定義します。 | |
− | == | + | <math> \mu_{ij} = \textstyle\sum^{\infty}_{n=1} nf^{(n)}_{ij}</math> |
− | < | + | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | + | ==定常分布== | |
+ | マルコフ連鎖の遷移行列<math>\mathbf P</math>に対して | ||
− | <math> | + | <math>\bar\pi = \bar\pi \mathbf P</math> |
− | \ | + | |
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | \ | + | |
− | \ | + | |
− | </math> | + | |
− | + | を満たし、要素の総和が 1 、つまり <math>\textstyle \sum_i \pi_i = 1</math> となるような行ベクトル<math>\bar\pi = (\pi_0, \pi_1, \ldots, \pi_n)</math>を定常分布 (stationary distribution) といいます。定常分布は '''P<sup>T</sup>''' の固有値 1 に対応する固有ベクトルともみなせます。状態数が有限の場合は 1 を必ず固有値に持つので定常分布が存在しますが、ただ一つに定まるとは限りません。 | |
− | + | ||
+ | ;例:無限個の定常分布を持つマルコフ連鎖 | ||
+ | 確率行列が n 次元の単位行列 '''I''' のとき、定常状態は無限にあります。固有値 λ (n個) は全て 1 で、このマルコフ連鎖は既約ではありません (reducible)。 | ||
+ | |||
+ | ;例:定常分布を持たないマルコフ連鎖 | ||
+ | 正の整数値に対応するマルコフ連鎖を仮定し、状態 i から i, i + 1, i + 2 ... にそれぞれ 1/2, 1/4, 1/8 ... の確率で遷移するとします。各状態が再帰不確実なため、定常状態 π はゼロベクトルになってしまいます。 | ||
<math> | <math> | ||
− | \begin{ | + | {\mathbf P} = |
− | + | \begin{bmatrix} | |
− | + | 1/2 & 1/4 & 1/8 & 1/16 & 1/32 & \cdots \\ | |
− | \ | + | 0 & 1/2 & 1/4 & 1/8 & 1/16 & \cdots \\ |
− | \end{ | + | 0 & 0 & 1/2 & 1/4 & & 1/8 & \cdots \\ |
+ | 0 & 0 & 0 & 1/2 & 1/4 & \cdots \\ | ||
+ | \vdots & \vdots & \vdots & \vdots | ||
+ | \end{bmatrix} | ||
</math> | </math> | ||
− | + | ===定常分布をもつ条件=== | |
− | + | ||
− | <math> \ | + | 既約で、再帰確実かつ非周期的(エルゴード的)なマルコフ連鎖は唯一つの定常分布 <math>\bar\pi</math> を持ち、 再帰時間の期待値との間に |
− | + | <math>\textstyle \pi_i = \lim_{t\rightarrow \infty} p^{(t)}_{ji} = 1/\mu_{ii} </math> | |
− | + | ||
− | + | ||
− | + | が成り立ちます。この証明および関連する定理は、[[Aritalab:Lecture/NetworkBiology/Markov Chains/StationaryDistribution|定常分布のページ]]を参照してください。 | |
+ | これは再帰時間の期待値が出発する状態 ''j'' に依存しないことを意味し、再帰までのステップ数期待値が <math>\mu_{ii}</math> ならば状態 ''i'' に戻ってくる確率が <math>1/\mu_{ii}</math> であることに対応します。定常状態において、各状態での存在確率は出発点に依存しません。 | ||
− | + | <math>\textstyle \lim_{t \rightarrow \infty} p^{(t)}_{ji} = | |
+ | \lim_{t \rightarrow \infty} p^{(t)}_{ii} = 1/\mu_{ii}</math> | ||
− | <math> | + | さらに定常分布においては、各状態に入る確率と出る確率が等しいことにも注意します。 |
− | + | つまり全ての状態 i, j に対し、i から出ていく確率の和は、i に入ってくる確率の和に等しく <math>\pi_i</math> になります。 | |
− | + | ||
− | \pi_i | + | |
− | + | ||
− | </math> | + | |
− | + | <math>\textstyle \sum^n_{j=0}\pi_i p_{ij} = \sum^n_{j=0}\pi_j p_{ji} = \pi_i</math> | |
− | <math>\ | + | エルゴード的であれば定常分布がただ一つに定まることを証明しましょう。 |
+ | 仮に定常分布が二つあるとして、もう一つの分布を <math>\bar\phi</math> と書きます。 | ||
+ | 定常分布であるから | ||
− | + | <math>\phi_i = \textstyle\sum_k \phi_k p^{(t)}_{ki} \xrightarrow{t \rightarrow \infty} | |
+ | \sum_k \phi_k \pi_i = \pi_i \sum_k \phi_k = \pi_i</math> | ||
− | === | + | すなわち<math>\bar \phi = \bar \pi</math>です。 |
− | + | ||
+ | ==参考・解説== | ||
+ | <references/> |
Latest revision as of 00:35, 21 October 2011
Wiki Top | Up one level | レポートの書き方 | Arita Laboratory |
|
ここではランダムウォークを考えるのに便利な概念を導入します。
[edit] マルコフ連鎖
離散確率過程は
を満たすときにマルコフ連鎖 (Markov chain) と呼ばれます。マルコフとはロシアの統計学者 Andrei A. Markov (1856-1922) のことで、マルコフ連鎖に関する多くの功績を残しました。状態 (state) が状態 のみに依存して決まる性質をマルコフ性 (Markov property) または無記憶性 (memoryless property) といいます。
マルコフ連鎖において状態 i から j への遷移確率を と書けば、マルコフ連鎖は遷移行列
で記述できます。[1] 遷移確率を表すので行列の行方向に足し合わせた値は必ず 1 になっており、確率行列 (stochastic matrix) と呼ばれます。もし行方向に足し合わせても 1 になる場合、二重確率行列 (doubly stochastic matrix) と呼ばれます。
記法を拡張し、i から j へ正確に m ステップで移る遷移確率を
と書きましょう。右肩にある (m) という表記は、m ステップ後という意味で m 乗ではありません。1ステップ目で移動した先を k と書くと であるから、遷移行列を m 乗すれば正確に m ステップで移った先を示す遷移行列を得ます(数学的帰納法)。また記法をそろえるために
と定義します。
[edit] チャップマン-コルモゴロフの等式
m ステップの遷移を、 s ステップと m − s ステップに分解する以下の式は、チャップマン-コルモゴロフの等式と呼ばれます[2]。
以下でも という式をよく使います。
[edit] 既約
状態 i から j へ何ステップかで到達できる場合、j は i から到達可能 (accessible) と呼びます。 互いに到達可能な状態 i, j どうしを連結 (communicate) しているといい、と書きます。連結性により同値類が形成されます。
- 反射律 (reflexivity): いかなる状態 i も、
- 対称律 (symmetry): なら
- 推移律 (transitivity): かつなら
全ての状態が同じ同値類 (communication class) に属すとき、つまり全ての頂点が互いに連結なとき、マルコフ連鎖は既約 (irreducible) といいます。既約なマルコフ連鎖とは、グラフ表現すると強連結 (strongly connected) になっていて、任意の頂点から任意の頂点に移動できる場合に相当します。
また、状態集合 C は、C に属すどの状態からも C 以外の状態に抜け出せないとき、閉じている (closed) といいます。例えば、グラフ表現した際に外に出る辺をもたない状態だけからなる集合は閉じています。
- 例: 1次元のウォーク
0 と N の間を左右に1ステップずつ移動し、0, N を吸収状態とするランダムウォークを考えます。0 から N までの状態は 3 つの同値類 {0}, {1, 2, ..., N−1}, {N} に分かれ、{0, N} は閉じています。
[edit] 周期性
状態 i に戻ってくるまでのステップ数が自然数 k (>1) の倍数回に限られ、しかも k がこの性質を持つ最大公約数の場合、状態 i は周期 k でといいます。 k = 1 のとき、状態は非周期的であるといいます。マルコフ連鎖の中で同じ同値類に属する (communicativeな) 状態 i, j は同じ周期をもちます[3]。
- 例:円周上のウォーク
円周上に配置された N 状態が一方向につながったマルコフ連鎖は、規約で周期 N を持ちます。遷移行列 P を N 乗すると、恒等行列 I になります。
- 例: 1次元のウォーク
原点からスタートして左右に1ステップずつ移動するウォークでは、原点に戻るまでのステップ数が必ず偶数です。つまり、状態 0 は周期 2 になります。いずれの状態も周期は 2 です。
[edit] 再帰性
状態 i から出発し時刻 t になって初めて j に到達する確率をと書くことにします。 前出のは複数回 j を訪れることを許すため、となります。
[edit] 再帰時間
同じ状態に初めて戻る確率 を初再帰確率 (first return probability) と呼び と定義します。状態 i は
- であれば再帰不確実 (transient)
- であれば再帰確実 (recurrent)
と呼びます。全ての状態が再帰確実であれば、マルコフ連鎖自体を再帰確実と呼びます。
[edit] 平均初再帰時間 MFRT
状態 i における平均初再帰時間 (mean first return time または mean recurrence time) を
と書きます。状態 i が再帰不確実な場合は です。
状態 i が再帰確実でも が有限とは限りません。初再帰時間の期待値が有限なとき有限再帰 (positive recurrent)、そうでない場合をゼロ再帰 (null recurrent) と呼びます。ゼロ再帰性を満たすには無限の状態数が必要です。
- 例:2 × 2 行列
以下の確率行列を持つ 2 状態のマルコフ連鎖は有限再帰的です。
直感的には 2 状態の間を自由に行き来できるため、必ず戻ってきます[4] 。
- 例:ゼロ再帰的なマルコフ連鎖
正の整数値に対応するマルコフ連鎖を仮定し、状態 i から確率 i/(i + 1) で状態 i + 1 に、確率 1/(i + 1) で状態 1 に移動するとします。
高い確率で無限遠に進んでいけるため、状態 1 に初めて戻るまでの期待値は無限大でゼロ再帰的です[5]。
[edit] 通過時間、平均初通過確率 MFPT
状態 i から始めて j に最初に訪れる確率 を初通過確率 (first passage time probability) と呼び、 と定義します。平均初通過時間 (mean first passage time; MFPT) も同様に定義します。
[edit] 定常分布
マルコフ連鎖の遷移行列に対して
を満たし、要素の総和が 1 、つまり となるような行ベクトルを定常分布 (stationary distribution) といいます。定常分布は PT の固有値 1 に対応する固有ベクトルともみなせます。状態数が有限の場合は 1 を必ず固有値に持つので定常分布が存在しますが、ただ一つに定まるとは限りません。
- 例:無限個の定常分布を持つマルコフ連鎖
確率行列が n 次元の単位行列 I のとき、定常状態は無限にあります。固有値 λ (n個) は全て 1 で、このマルコフ連鎖は既約ではありません (reducible)。
- 例:定常分布を持たないマルコフ連鎖
正の整数値に対応するマルコフ連鎖を仮定し、状態 i から i, i + 1, i + 2 ... にそれぞれ 1/2, 1/4, 1/8 ... の確率で遷移するとします。各状態が再帰不確実なため、定常状態 π はゼロベクトルになってしまいます。
[edit] 定常分布をもつ条件
既約で、再帰確実かつ非周期的(エルゴード的)なマルコフ連鎖は唯一つの定常分布 を持ち、 再帰時間の期待値との間に
が成り立ちます。この証明および関連する定理は、定常分布のページを参照してください。 これは再帰時間の期待値が出発する状態 j に依存しないことを意味し、再帰までのステップ数期待値が ならば状態 i に戻ってくる確率が であることに対応します。定常状態において、各状態での存在確率は出発点に依存しません。
さらに定常分布においては、各状態に入る確率と出る確率が等しいことにも注意します。 つまり全ての状態 i, j に対し、i から出ていく確率の和は、i に入ってくる確率の和に等しく になります。
エルゴード的であれば定常分布がただ一つに定まることを証明しましょう。 仮に定常分布が二つあるとして、もう一つの分布を と書きます。 定常分布であるから
すなわちです。
[edit] 参考・解説
- ↑ 状態 i から j への遷移確率を pij とする記法が主流ですが (Karlin & Taylor 1975)、Linda JS Allen (2011 2nd Ed) では j から i への遷移確率を pij と定義しています。そうすると定常分布を考える際に 以下で書くように行ベクトル π を用いて とするのではなく、列ベクトルを用いて と書けるようになります。記法上の問題であり、本質はかわりません。
- ↑
- チャップマン-コルモゴロフの等式の証明
- ↑
- 同じ同値類に属する状態の周期が等しいことの証明
- ↑
- 例:2 × 2 行列が正再帰的になることの証明
- ↑
- ゼロ再帰性の証明