Aritalab:Lecture/NetworkBiology/Markov Chains - Revision history

Adm: /* 定常分布をもつ条件 */

2011-10-20T15:35:44Z

‎定常分布をもつ条件

Adm: /* 定常分布 */

2011-10-20T15:14:36Z

‎定常分布

Adm: /* 平均初再帰時間 MFRT */

2011-10-20T15:07:08Z

‎平均初再帰時間 MFRT

Adm: /* 再帰時間 */

2011-10-20T15:02:50Z

‎再帰時間

Adm: /* 周期性 */

2011-10-20T15:00:47Z

‎周期性

Adm: /* 定常分布をもつ条件 */

2011-10-18T01:18:58Z

‎定常分布をもつ条件

Adm at 02:45, 17 October 2011

2011-10-17T02:45:00Z

Adm: /* 定常分布をもつ条件 */

2011-10-16T10:52:37Z

‎定常分布をもつ条件

Adm: /* 定常分布をもつ条件 */

2011-10-15T08:22:43Z

‎定常分布をもつ条件

Adm: /* 定常分布をもつ条件 */

2011-10-15T08:21:24Z

‎定常分布をもつ条件

@@ Line 210: / Line 210: @@
 <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> であることに対応します。定常状態において、各状態での存在確率は出発点に依存しません。

@@ Line 185: / Line 185: @@
 <math>\bar\pi = \bar\pi \mathbf P</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 を必ず固有値に持つので定常分布が存在しますが、ただ一つとは限りません。
+を満たし、要素の総和が 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''' のとき、定常状態は無限にあります。固有値 &lambda; (n個) は全て 1 で、このマルコフ連鎖は既約ではありません (reducible)。
-;定常分布を持たない例
+;例：定常分布を持たないマルコフ連鎖
-正の整数値に対応するマルコフ連鎖を仮定し、状態 i から i, i + 1, i + 2 ... にそれぞれ 1/2, 1/4, 1/8 ... の確率で遷移するとします。各状態が非再帰的のため、定常状態 &pi; はゼロベクトルになってしまいます。
+正の整数値に対応するマルコフ連鎖を仮定し、状態 i から i, i + 1, i + 2 ... にそれぞれ 1/2, 1/4, 1/8 ... の確率で遷移するとします。各状態が再帰不確実なため、定常状態 &pi; はゼロベクトルになってしまいます。
 <math>
@@ Line 206: / Line 206: @@
 ===定常分布をもつ条件===
-既約で再帰的かつ非周期的（エルゴード的）なマルコフ連鎖は唯一つの定常分布 <math>\bar\pi</math> を持ち、 再帰時間の期待値との間に
+既約で、再帰確実かつ非周期的（エルゴード的）なマルコフ連鎖は唯一つの定常分布 <math>\bar\pi</math> を持ち、 再帰時間の期待値との間に
-<math>\textstyle \pi_i = \lim_{t\rightarrow \infty} p^{(t)}_{ji} = \frac{1}{\mu_{ii}} </math>
+<math>\textstyle \pi_i = \lim_{t\rightarrow \infty} p^{(t)}_{ji} = 1/\mu_{ii} </math>
 が成り立ちます。
-これは再帰時間の期待値が出発する状態 ''j'' に依存しないことを意味し、再帰までのステップ数期待値が <math>\mu_{ii}</math> ならば状態 ''i'' に戻ってくる確率が <math>1/\mu_{ii}</math> であることに対応します。つまり各状態における存在確率は出発点に依存しません。
+これは再帰時間の期待値が出発する状態 ''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} = \frac{1}{\mu_{ii}}</math>
+\lim_{t \rightarrow \infty} p^{(t)}_{ii} = 1/\mu_{ii}</math>
 さらに定常分布においては、各状態に入る確率と出る確率が等しいことにも注意します。
-つまり全ての状態 i, j に対し、i から
+つまり全ての状態 i, j に対し、i から出ていく確率の和は、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>

@@ Line 108: / Line 108: @@
 <math>\mu_{ii} = \textstyle\sum^{\infty}_{t=1} tf^{(t)}_{ii}</math>
-と書きます。状態 ''i'' が過渡的な場合は <math>\mu_{ii} = \infty</math> です。
+と書きます。状態 ''i'' が再帰不確実な場合は <math>\mu_{ii} = \infty</math> です。
-状態 ''i'' が再帰的でも <math>\mu_{ii}</math> が有限とは限りません。初再帰時間の期待値が有限なとき正再帰的 (positive recurrent)、そうでない場合をゼロ再帰的 (null recurrent) と呼びます。ゼロ再帰性を満たすには無限の状態数が必要です。状態数が有限 ( n 個) であれば、多くとも n + 1 ステップ目には既に訪れた状態を再び訪れます。
+状態 ''i'' が再帰確実でも <math>\mu_{ii}</math> が有限とは限りません。初再帰時間の期待値が有限なとき有限再帰 (positive recurrent)、そうでない場合をゼロ再帰 (null recurrent) と呼びます。ゼロ再帰性を満たすには無限の状態数が必要です。
 ;例：2 &times; 2 行列
-以下の確率行列を持つ 2 状態のマルコフ連鎖は正再帰的です。
+以下の確率行列を持つ 2 状態のマルコフ連鎖は有限再帰的です。
 <math>
@@ Line 124: / Line 124: @@
 </math>
-直感的には 2 状態の間を行き来できるため、必ず戻ってきます<ref>
+直感的には 2 状態の間を自由に行き来できるため、必ず戻ってきます<ref>
 ;例：2 &times; 2 行列が正再帰的になることの証明
 確率行列は行方向の和が必ず 1 になるため、行列の要素は全て正の値をとります。一般に n &ge; 3 について
@@ Line 168: / Line 168: @@
 <math>\textstyle \prod^t_{j=1} \frac{j}{j+1} = \frac{1}{t+1} \xrightarrow{t \rightarrow \infty} 0</math>
-したがって状態 1 は再帰的で <math>\textstyle f^{(t)}_{11} = \frac{1}{t (t + 1)}</math> （''t'' &minus; 1 ステップ 1 に戻らず、''t'' ステップ目で 1 に戻る）。しかし、状態 1 に初めて戻るまでの期待値は無限大。
+したがって状態 1 は再帰確実 <math>\textstyle f^{(t)}_{11} = \frac{1}{t (t + 1)}</math> （''t'' &minus; 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>

@@ Line 99: / Line 99: @@
 ===再帰時間===
 同じ状態に初めて戻る確率 <math>f^{(t)}_{ii}</math> を初再帰確率 (first return probability) と呼び<math>f^{(0)}_{ii} = 0</math> と定義します。状態 ''i'' は
-: <math>\textstyle \sum_{t=1}^{\infty} f^{(t)}_{ii} < 1</math>であれば過渡的 (transient)
+: <math>\textstyle \sum_{t=1}^{\infty} f^{(t)}_{ii} < 1</math>であれば再帰不確実 (transient)
-: <math>\textstyle \sum_{t=1}^{\infty} f^{(t)}_{ii} = 1</math>であれば再帰的 (recurrent)
+: <math>\textstyle \sum_{t=1}^{\infty} f^{(t)}_{ii} = 1</math>であれば再帰確実 (recurrent)
-と呼びます。全ての状態が再帰的であれば、マルコフ連鎖自体を再帰的と呼びます。
+と呼びます。全ての状態が再帰確実であれば、マルコフ連鎖自体を再帰確実と呼びます。
 ===平均初再帰時間 MFRT===

@@ Line 90: / Line 90: @@
 ;例：円周上のウォーク
 円周上に配置された N 状態が一方向につながったマルコフ連鎖は、規約で周期 N を持ちます。遷移行列 '''P''' を N 乗すると、恒等行列 '''I''' になります。
 ==再帰性==

@@ Line 215: / Line 215: @@
 さらに定常分布においては、各状態に入る確率と出る確率が等しいことにも注意します。
-つまり全ての状態 ''i, j'' に対し、''i'' から
+つまり全ての状態 i, j に対し、i から
-<math>\textstyle \sum^n_{j=0}\pi_i p_{ij} = \sum^0_{j=0}\pi_j p_{ji} = \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>\bar\phi</math> と書きます。
 定常分布であるから
-<math>\phi_i = \sum_k \phi_k p^{(t)}_{ki} \xrightarrow{t \rightarrow \infty}
+<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>

@@ Line 204: / Line 204: @@
 ===定常分布をもつ条件===
-マルコフ連鎖をこれまでの特徴に基づいて分類すると以下のようになります。
+既約で再帰的、非周期的（エルゴード的）なマルコフ連鎖は唯一つの定常分布 <math>\bar\pi</math> を持ち、 再帰時間の期待値との間に
-* 既約 or 非既約
-* 正再帰的 or ゼロ再帰的 or 非再帰的
-* 周期的 or 非周期的
-−
-有限のマルコフ連鎖
-−
-既約でエルゴード的なマルコフ連鎖は唯一つの定常分布 <math>\bar\pi</math> を持ち、 再帰時間の期待値との間に
 <math>\textstyle \pi_i = \lim_{t\rightarrow \infty} p^{(t)}_{ji} = \frac{1}{\mu_{ii}} </math>