Aritalab:Lecture/NetworkBiology/Markov Chains
m |
|||
Line 1: | Line 1: | ||
{{Lecture/Header}} | {{Lecture/Header}} | ||
+ | ここではランダムウォークを考えるのに便利な概念を導入します。 | ||
==マルコフ連鎖== | ==マルコフ連鎖== | ||
− | |||
離散確率過程<math>X_0, X_1, X_2 \ldots</math>は | 離散確率過程<math>X_0, X_1, X_2 \ldots</math>は | ||
Line 12: | Line 12: | ||
を満たすときにマルコフ連鎖 (Markov chain) と呼ばれる。状態 (state) <math>X_t</math> が状態 <math>X_{t-1}</math> のみに依存して決まる性質をマルコフ性 (Markov property) または無記憶性 (memoryless property) という。 | を満たすときにマルコフ連鎖 (Markov chain) と呼ばれる。状態 (state) <math>X_t</math> が状態 <math>X_{t-1}</math> のみに依存して決まる性質をマルコフ性 (Markov property) または無記憶性 (memoryless property) という。 | ||
− | マルコフ連鎖において状態 ''i'' から ''j'' への遷移確率を<math>p_{i,j} = \mbox{Pr}(X_t = j | X_{t-1} = i )</math>と書けば、マルコフ連鎖は遷移行列 | + | マルコフ連鎖において状態 ''i'' から ''j'' への遷移確率を<math>p_{i,j} = \mbox{Pr}(X_t = j | X_{t-1} = i )</math> と書けば、マルコフ連鎖は遷移行列 |
<math> | <math> | ||
Line 30: | Line 30: | ||
と書こう。1ステップ目で移動した先を ''k'' と書くと | と書こう。1ステップ目で移動した先を ''k'' と書くと | ||
− | <math>\textstyle p_{i,j}^m = \sum_{k} p_{i,k} p^{m-1}_{k,j} </math> | + | <math>\textstyle p_{i,j}^m = \sum_{k} p_{i,k} \cdot p^{m-1}_{k,j} </math> |
であるから、遷移行列<math>{\mathbf P}</math>を ''m'' 乗すれば正確に ''m'' ステップで移った先を示す遷移行列を得る(数学的帰納法)。 | であるから、遷移行列<math>{\mathbf P}</math>を ''m'' 乗すれば正確に ''m'' ステップで移った先を示す遷移行列を得る(数学的帰納法)。 | ||
Line 56: | Line 56: | ||
状態 ''i'' が再帰的であっても、再帰までのステップ数(再帰時間)の期待値 <math>M_{i,i}</math> が有限とは限らない。 | 状態 ''i'' が再帰的であっても、再帰までのステップ数(再帰時間)の期待値 <math>M_{i,i}</math> が有限とは限らない。 | ||
− | 例えば正の整数値に対応するマルコフ連鎖を仮定し、状態 ''i'' から確率 | + | 例えば正の整数値に対応するマルコフ連鎖を仮定し、状態 ''i'' から確率 ''i''/(''i'' +1) で状態 ''i'' +1 に、確率 1/(''i'' +1) で状態 1 に移動する系を考えよう。 |
− | + | 状態 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 \prod^t_{j=1} \frac{j}{j+1} = \frac{1}{t+1} \xrightarrow{t \rightarrow \infty} 0</math> | ||
− | + | したがって状態 1 は再帰的で、<math>r^t_{1,1}</math> = 1/''t'' (''t'' +1)。 | |
− | + | しかし初めて状態 1 に戻ってくるまでのステップ数の期待値は | |
<math>\textstyle M_{1,1} = \sum^{\infty}_{t=1} t \cdot r^t_{1,1} = \sum^{\infty}_{t=1} \frac{1}{t+1} \xrightarrow{t \rightarrow \infty} \infty</math> | <math>\textstyle M_{1,1} = \sum^{\infty}_{t=1} t \cdot r^t_{1,1} = \sum^{\infty}_{t=1} \frac{1}{t+1} \xrightarrow{t \rightarrow \infty} \infty</math> | ||
− | 再帰時間の期待値が有限な状態を正再帰的 (positive recurrent) | + | 再帰時間の期待値が有限な状態を正再帰的 (positive recurrent)、そうでない場合をゼロ再帰的 (null recurrent) とよぶ。 |
− | + | ゼロ再帰性を満たすには無限の状態数が必要になる。 | |
状態数が ''N'' 個で有限の場合、少なくとも ''N+1'' ステップ目に既に訪れた状態に辿り着く。 | 状態数が ''N'' 個で有限の場合、少なくとも ''N+1'' ステップ目に既に訪れた状態に辿り着く。 | ||
− | + | よって少なくとも一つの再帰的な状態が存在しなくてはならない。そして再帰的な状態であれば、状態数が有限なので必ず正再帰的である。 | |
===周期性=== | ===周期性=== | ||
状態 ''i'' に戻ってくるまでのステップ数が自然数 ''k'' (>1) の倍数回に限られ、しかも ''k'' がこの性質を持つ最大値の場合、状態 ''i'' は周期 ''k'' であるという。 | 状態 ''i'' に戻ってくるまでのステップ数が自然数 ''k'' (>1) の倍数回に限られ、しかも ''k'' がこの性質を持つ最大値の場合、状態 ''i'' は周期 ''k'' であるという。 | ||
''k=1'' のとき、状態は非周期的であるという。 | ''k=1'' のとき、状態は非周期的であるという。 | ||
− | 全ての状態が非周期的で正再帰的なマルコフ連鎖を、エルゴード的 (ergodic) | + | |
+ | ===エルゴード的=== | ||
+ | 全ての状態が非周期的で正再帰的なマルコフ連鎖を、エルゴード的 (ergodic) であるという。有限で規約かつ非周期的なマルコフ連鎖はエルゴード的になる。なぜなら、規約という条件で少なくとも一つの再帰的な状態が存在するため、全ての状態が再帰的になる。さらに有限なため、すべての状態が正再帰的といえるからである。 | ||
===定常分布=== | ===定常分布=== | ||
Line 81: | Line 83: | ||
<math>\bar\pi = \bar\pi \mathbf P</math> | <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) という。 | |
既約でエルゴード的なマルコフ連鎖は唯一つの定常分布 <math>\bar\pi</math> を持ち、 再帰時間の期待値との間に | 既約でエルゴード的なマルコフ連鎖は唯一つの定常分布 <math>\bar\pi</math> を持ち、 再帰時間の期待値との間に | ||
Line 93: | Line 95: | ||
さらに定常分布においては、各状態に入る確率と出る確率が等しいことにも注意する。 | さらに定常分布においては、各状態に入る確率と出る確率が等しいことにも注意する。 | ||
− | + | つまり全ての状態 ''i, j'' に対し、''i'' から | |
− | <math>\textstyle \pi_i p_{i,j} = \pi_j p_{j, i} </math> | + | <math>\textstyle \sum^n_{j=0}\pi_i p_{i,j} = \sum^0{j=0}\pi_j p_{j, i} = \pi_i</math> |
− | + | 定常分布がただ一つに定まることを証明しよう。 | |
仮に定常分布が二つあるとして、もう一つの分布を <math>\bar\phi</math> と書く。 | 仮に定常分布が二つあるとして、もう一つの分布を <math>\bar\phi</math> と書く。 | ||
定常分布であるから | 定常分布であるから | ||
Line 110: | Line 112: | ||
窓口に並ぶ客の人数 ''i'' をモデルしよう。 | 窓口に並ぶ客の人数 ''i'' をモデルしよう。 | ||
単位時間において以下の事象が発生する。 | 単位時間において以下の事象が発生する。 | ||
− | * もし ''i < n'' だったら、確率 | + | * もし ''i < n'' だったら、確率 ''α'' で客が一人増える。 |
− | * もし ''i > 0''なら、確率 | + | * もし ''i > 0'' なら、確率 ''β'' で先頭から順に客は減る。 |
* それ以外の場合、客の数は変化しない。 | * それ以外の場合、客の数は変化しない。 | ||
− | 時刻 ''t'' | + | 時刻 ''t'' における行列の長さを考えると、有限のマルコフ連鎖になっている。遷移確率は以下のようになる。 |
<math> | <math> | ||
Line 144: | Line 146: | ||
<math> \pi_i = \frac{ (\alpha/\beta)^i }{\sum^n_{i=0} (\alpha/\beta)^i} </math> | <math> \pi_i = \frac{ (\alpha/\beta)^i }{\sum^n_{i=0} (\alpha/\beta)^i} </math> | ||
+ | |||
+ | ;結論 | ||
+ | * ''α'' > ''β'' のときは行列が長い確率の方が大きい | ||
+ | * ''α'' = ''β'' のとき、行列の長さは0からnまで等確率 | ||
+ | |||
+ | 同じ結果は、定常状態において ''α π<sub>i</sub>'' = ''β π''<sub>''i'' +1</sub> という考察からも導くことができる。''π<sub>i</sub>'' = (''α/β'') ''π''<sub>''i'' +1</sub> から帰納法で ''π<sub>i</sub>'' = ''π<sub>0</sub>''(''α/β'')<sup>''i''</sup> となる。 | ||
+ | |||
+ | 列の長さに上限 ''n'' が無い場合、マルコフ連鎖は有限ではない。もし定常分布があるとしたら(ない可能性もある) | ||
+ | |||
+ | <math> | ||
+ | \begin{align} | ||
+ | \pi_0 &= (1 - \alpha) \pi_0 + \beta \pi_1 \\ | ||
+ | \pi_i &= \alpha \pi_{i-1} + (1 -\alpha -\beta) \pi_i + \beta \pi_{i+1} \ (i \geq 1) | ||
+ | \end{align} | ||
+ | </math> | ||
+ | |||
+ | の解が存在しなくてはならない。前出の解から類推して | ||
+ | |||
+ | <math>\pi_i = \frac{ (\alpha/\beta)^i }{\sum^\infty_{i=0} (\alpha/\beta)^i} = \Big(\frac{\alpha}{\beta}\Big)^i\Big(1-\frac{\alpha}{\beta}\Big)</math> | ||
+ | |||
+ | が答えになる。このとき ''α'' < ''β'' でないと定常分布は存在しない。 | ||
===出生死亡過程=== | ===出生死亡過程=== | ||
[[Aritalab:Lecture/NetworkBiology/Markov Chains/Birth-death Process|このページ]]を参照。 | [[Aritalab:Lecture/NetworkBiology/Markov Chains/Birth-death Process|このページ]]を参照。 |
Revision as of 09:59, 19 May 2011
Wiki Top | Up one level | レポートの書き方 | Arita Laboratory |
|
ここではランダムウォークを考えるのに便利な概念を導入します。
マルコフ連鎖
離散確率過程は
を満たすときにマルコフ連鎖 (Markov chain) と呼ばれる。状態 (state) が状態 のみに依存して決まる性質をマルコフ性 (Markov property) または無記憶性 (memoryless property) という。
マルコフ連鎖において状態 i から j への遷移確率を と書けば、マルコフ連鎖は遷移行列
で記述できる。記法を拡張し、i から j へ正確に m ステップで移る遷移確率を
と書こう。1ステップ目で移動した先を k と書くと であるから、遷移行列を m 乗すれば正確に m ステップで移った先を示す遷移行列を得る(数学的帰納法)。
これから考えたいのは、ネットワーク上を遷移行列に従って無限時間移動した際の、各状態における存在確率(定常分布)である。 ただし、ユニークな定常分布が存在するためにはこれから述べる規約、再帰性、非周期性という概念が必要になる。
既約
状態 i から j へ何ステップかで到達できる場合、j は i から到達可能 (accessible) と呼ぶ。 互いに到達可能な状態 i, j どうしを連結 (communicate) しているといい、と書く。連結性は同値類を形成する。
- 反射律: いかなる状態 i も、
- 対称律: なら
- 推移律: かつなら
全ての状態が同じ同値類に属すとき、つまり全ての頂点が互いに連結なとき、マルコフ連鎖は既約 (irreducible) という。既約なマルコフ連鎖は、グラフ表現すると強連結 (strongly connected) になっていて、任意の頂点から任意の頂点に移動できる。
再帰性
状態 i から出発し時刻 t になって初めて j に到達する確率をと書く。 前出のは複数回 j を訪れることを許すため、となることに注意しよう。
状態 i を
- であれば一時的 (transient)
- であれば再帰的 (recurrent)
と呼ぶ。全ての状態が再帰的であれば、マルコフ連鎖自体を再帰的と呼ぶ。
状態 i が再帰的であっても、再帰までのステップ数(再帰時間)の期待値 が有限とは限らない。 例えば正の整数値に対応するマルコフ連鎖を仮定し、状態 i から確率 i/(i +1) で状態 i +1 に、確率 1/(i +1) で状態 1 に移動する系を考えよう。 状態 1 からスタートして最初の t ステップで 1 に戻らない確率は
したがって状態 1 は再帰的で、 = 1/t (t +1)。 しかし初めて状態 1 に戻ってくるまでのステップ数の期待値は
再帰時間の期待値が有限な状態を正再帰的 (positive recurrent)、そうでない場合をゼロ再帰的 (null recurrent) とよぶ。 ゼロ再帰性を満たすには無限の状態数が必要になる。 状態数が N 個で有限の場合、少なくとも N+1 ステップ目に既に訪れた状態に辿り着く。 よって少なくとも一つの再帰的な状態が存在しなくてはならない。そして再帰的な状態であれば、状態数が有限なので必ず正再帰的である。
周期性
状態 i に戻ってくるまでのステップ数が自然数 k (>1) の倍数回に限られ、しかも k がこの性質を持つ最大値の場合、状態 i は周期 k であるという。 k=1 のとき、状態は非周期的であるという。
エルゴード的
全ての状態が非周期的で正再帰的なマルコフ連鎖を、エルゴード的 (ergodic) であるという。有限で規約かつ非周期的なマルコフ連鎖はエルゴード的になる。なぜなら、規約という条件で少なくとも一つの再帰的な状態が存在するため、全ての状態が再帰的になる。さらに有限なため、すべての状態が正再帰的といえるからである。
定常分布
マルコフ連鎖の遷移行列に対して
を満たし、要素の総和が 1 、つまり となるような行ベクトルを定常分布 (stationary distribution) という。 既約でエルゴード的なマルコフ連鎖は唯一つの定常分布 を持ち、 再帰時間の期待値との間に
が成り立つ。 これは再帰時間の期待値が出発する状態 j に依存しないことを意味し、再帰までのステップ数期待値が ならば状態 i に戻ってくる確率が であることに対応する。つまり各状態における存在確率は出発点に依存しない。
さらに定常分布においては、各状態に入る確率と出る確率が等しいことにも注意する。 つまり全ての状態 i, j に対し、i から
定常分布がただ一つに定まることを証明しよう。 仮に定常分布が二つあるとして、もう一つの分布を と書く。 定常分布であるから
すなわちとなる。
マルコフ連鎖の例
待ち行列
窓口に並ぶ客の人数 i をモデルしよう。 単位時間において以下の事象が発生する。
- もし i < n だったら、確率 α で客が一人増える。
- もし i > 0 なら、確率 β で先頭から順に客は減る。
- それ以外の場合、客の数は変化しない。
時刻 t における行列の長さを考えると、有限のマルコフ連鎖になっている。遷移確率は以下のようになる。
マルコフ連鎖は既約、有限、非周期的なので唯一の定常分布 を持つ。 満たすべき式は
これを解くと 。 更に より
- 結論
- α > β のときは行列が長い確率の方が大きい
- α = β のとき、行列の長さは0からnまで等確率
同じ結果は、定常状態において α πi = β πi +1 という考察からも導くことができる。πi = (α/β) πi +1 から帰納法で πi = π0(α/β)i となる。
列の長さに上限 n が無い場合、マルコフ連鎖は有限ではない。もし定常分布があるとしたら(ない可能性もある)
の解が存在しなくてはならない。前出の解から類推して
が答えになる。このとき α < β でないと定常分布は存在しない。
出生死亡過程
このページを参照。