Aritalab:Lecture/NetworkBiology/Markov Chains/Birth-death Process - Revision history

Adm: /* 出生死亡過程 */

2015-08-28T03:10:59Z

‎出生死亡過程

Adm at 03:05, 28 August 2015

2015-08-28T03:05:59Z

Adm: /* 出生死亡過程 */

2013-02-01T00:39:10Z

‎出生死亡過程

Adm: /* ネットワーク上のゲーム */

2011-06-02T00:23:35Z

‎ネットワーク上のゲーム

Adm at 20:24, 1 June 2011

2011-06-01T20:24:54Z

Adm: /* モラン過程と同等なネットワーク */

2011-06-01T20:04:43Z

‎モラン過程と同等なネットワーク

Adm: /* モラン過程と同等なネットワーク */

2011-06-01T19:49:04Z

‎モラン過程と同等なネットワーク

Adm: /* 固定確率を低めるネットワーク */

2011-06-01T18:54:52Z

‎固定確率を低めるネットワーク

Adm: /* モラン過程 */

2011-06-01T18:53:54Z

‎モラン過程

Adm: /* モラン過程と同等なネットワーク */

2011-06-01T18:35:35Z

‎モラン過程と同等なネットワーク

@@ Line 8: / Line 8: @@
 ==出生死亡過程==
 ===モラン過程===
-個体数を ''N'' とし、状態 ''i'' から ''i'' + 1, ''i'' &minus; 1 の状態へそれぞれ確率<math>\alpha, \beta</math> <math>(\alpha + \beta < 1)</math>で遷移する場合を考える。
+個体数を ''N'' とし、状態 ''i'' から ''i'' + 1, ''i'' &minus; 1 の状態へそれぞれ確率 α, β ( α + β < 1) で遷移する場合を考えましょう。
-また状態 0 と ''N'' は吸収状態とする。（従ってユニークな定常分布を考えるわけではない。）
+また状態 0 と ''N'' は吸収状態とします。（従ってユニークな定常分布を考えるわけではない。）
-このマルコフ連鎖を1958年にモデルを発表した遺伝学者PAP MoranにちなんでMoran過程という。
+このマルコフ連鎖を、1958年にモデルを発表した遺伝学者PAP MoranにちなんでMoran過程といいます。
-状態 ''i'' から出発して状態 ''N'' に到達する確率を <math>x_i</math> と書く。これを固定確率と呼ぶ。
+状態 ''i'' から出発して状態 ''N'' に到達する確率を <math>x_i</math> と書き、これを固定確率と呼びます。
 <math>
@@ Line 32: / Line 32: @@
 </math>
-を導入すると
+を導入します。
 <math>\textstyle y_{i+1} = \gamma y_i, \quad \sum^N_{i=1} y_i = 1</math>
-を得る。Moran過程では通常、少ない個体数から N 個体にまで増殖するケースを考えるため、&gamma; は 1 より小さい値 ( つまり &beta; < &alpha; ) と考えてよい。
+Moran過程では通常、少ない個体数から N 個体にまで増殖するケースを考えるため、&gamma; は 1 より小さい値 ( つまり &beta; < &alpha; ) と考えてよいでしょう。
 <math> y_1 = x_1, \ y_2 = \gamma x_1, \ y_3 = \gamma^2 x_1, \cdots, y_n = \gamma^{N-1} x_1 </math>
@@ Line 57: / Line 57: @@
 </math>
-とあわせて
+とあわせて以下のようになります。
 <math>
@@ Line 64: / Line 64: @@
 </math>
 ===式の解釈===

← Older revision		Revision as of 03:05, 28 August 2015
Line 150:		Line 150:

	適応度がMoran過程に比べて <math>r^2</math> に増幅されていることがわかる。この議論の詳細な解析は、冒頭の参考文献 (Broom & Rychtar) を参照のこと。		適応度がMoran過程に比べて <math>r^2</math> に増幅されていることがわかる。この議論の詳細な解析は、冒頭の参考文献 (Broom & Rychtar) を参照のこと。
−
−	~~==ネットワーク上のゲーム==~~
−
−	~~各頂点は協力 (C: Cooperate) か裏切り (D: Defect) のいずれかの戦略を取るとする。~~
−	~~協力者は隣接頂点それぞれにコスト (cost) ''c'' を支払い、隣接する頂点は利得 (benefit) ''b'' を受け取る。~~
−	~~裏切る場合はコストを払わず、隣からの利得のみを受け取る。~~
−	~~頂点の適応度 (fitness) を支払いと利得の合計で判断し、戦略を更新する方法として以下の2通りを考えよう。~~
−	~~# 出生死亡過程: 単位時間毎に適応度に応じて頂点を選択し、隣接頂点をランダムに選んで同じ戦略へとコピーする。~~
−	~~# 死亡出生過程: 単位時間毎に頂点がランダムに選ばれて死亡する。隣接する頂点がそれぞれの適応度に応じて自分の戦略をその頂点にコピーする。~~
−
−	~~===一次元格子===~~
−	~~もっとも単純なケースとして単純サイクルを考える。~~
−
−	~~;出生死亡過程の場合~~
−	~~:C戦略とD戦略をとる頂点の境界部分にある2頂点を考慮すればよい。~~
−	~~<math>~~
−	~~\begin{matrix}~~
−	~~\longleftrightarrow & \circledcirc & \longleftrightarrow & \circledcirc & \longleftrightarrow & \circledast & \longleftrightarrow & \circledast & \longleftrightarrow\\~~
−	~~& & & -2c + b & & b & & &~~
−	~~\end{matrix}</math>~~
−
−	C戦略の端にいる頂点は、隣接する2頂点分のコストを払って利得を片側からしか得ないので合計は ''b'' − 2''c'' になるが、D戦略の端にいる頂点は利得 ''b'' を得られるので、いかなる ''b, c'' であってもD戦略が優位になる。
−
−	~~;死亡出生過程の場合~~
−	~~:C戦略とD戦略をとる頂点の境界部分から2つ離れたところまでの合計4頂点を考慮する。~~
−	~~<math>~~
−	~~\begin{matrix}~~
−	~~\longleftrightarrow & \circledcirc & \longleftrightarrow & \circledcirc & \longleftrightarrow & \circledast & \longleftrightarrow & \circledast & \longleftrightarrow\\~~
−	~~& 2(b - c) & & -2c + b & & b & & 0 &~~
−	~~\end{matrix}</math>~~
−
−	~~C戦略を取る側は、D戦略と隣接する頂点が ''b'' − 2 ''c''、そのまた隣は 2(''b'' − ''c'')になる。~~
−	~~D戦略を取る側は、C戦略と隣接する頂点が ''b''、そのまた隣は 0 になる。~~
−
−	~~従って ''b'' / ''c'' > 2 の場合はC戦略が優位。~~
−	~~一般化すると、次数 ''k'' の格子であれば <math> b/c > k</math>の場合にC戦略が優位になる。~~

@@ Line 36: / Line 36: @@
 <math>\textstyle y_{i+1} = \gamma y_i, \quad \sum^N_{i=1} y_i = 1</math>
-を得る。Moran過程では通常、少ない個体数から ''N'' 個体にまで増殖するケースを考えるため、<math>\gamma</math>は 1 より小さい値 ( つまり ''&beta;'' > ''&alpha;'' ) と考えてよい。
+を得る。Moran過程では通常、少ない個体数から N 個体にまで増殖するケースを考えるため、&gamma; は 1 より小さい値 ( つまり &beta; < &alpha; ) と考えてよい。
 <math> y_1 = x_1, \ y_2 = \gamma x_1, \ y_3 = \gamma^2 x_1, \cdots, y_n = \gamma^{N-1} x_1 </math>
@@ Line 67: / Line 67: @@
 ===式の解釈===
-''N'' 個体の集団において、全ての個体が最初タイプ　A　であるとする。
-このときタイプ　B　という突然変異が　1　個生じたとする。
+N 個体の集団において、全ての個体が最初タイプ　A　であるとする。
-タイプ　B　が <math>\gamma < 1</math>　を満たす、すなわち　<math>\alpha</math>　が　<math>\beta</math>　よりも大きくて個体数を増やす傾向にあると仮定する。
+このときタイプ B という突然変異が 1 個生じたとする。
 タイプ　B　が何らかの優性種であると考えてもよい。
 初めに　1　個生じたタイプBが集団 ''N'' の中に固定される（集団全体をカバーする）確率はモラン過程より　<math>x_1 \xrightarrow{N \rightarrow \infty} 1 - \gamma</math> になる。
-つまり、A より10倍優位な変異体であっても (<math>\gamma = 1/10</math>)、集団全体にその変異が保持される確率は 9/10 でしかない。
+つまり、A より10倍優位な変異体であっても (&gamma; = 1/10)、集団全体にその変異が保持される確率は 9/10 でしかない。
 通常の遺伝子変異で生存戦略に極めて優性となるケースは非常に稀だと考えられる。そうすると、優性な変異が集団全体に保持される可能性はそう大きくない。
@@ Line 80: / Line 81: @@
 ほとんどの遺伝子の突然変異は、自然淘汰において有利でも不利でもないとする[http://www.nig.ac.jp/museum_080501/evolution/C/bunsi-02.html 中立進化説]は当時大きな反響を呼んだ。
-突然変異が完全に中立な場合、<math>\gamma = 1</math>　となり左右に均等なランダムウォークになる。
+突然変異が完全に中立な場合、&gamma; = 1 となり左右に均等なランダムウォークになる。
 このとき <math>x_1 = 1/N</math> となる（[[Aritalab:Lecture/NetworkBiology/Random Walk|ランダムウォーク]]のギャンブラー破産問題を参照）。
 各個体の子孫がそれぞれ集団全体をカバーする可能性があり、各個体が均等な機会を持つから、これは当然の値ともいえる。

@@ Line 159: / Line 159: @@
 # 死亡出生過程: 単位時間毎に頂点がランダムに選ばれて死亡する。隣接する頂点がそれぞれの適応度に応じて自分の戦略をその頂点にコピーする。
 もっとも単純なケースとして単純サイクルを考える。
 ;出生死亡過程の場合
 :C戦略とD戦略をとる頂点の境界部分にある2頂点を考慮すればよい。
-C戦略の端にいる頂点は、隣接する2頂点分のコストを払って利得を片側からしか得ないので合計は <math>b-2c</math> になるが、D戦略の端にいる頂点は利得 ''b'' を得られるので、いかなる ''b, c'' であってもD戦略が優位になる。
+<math>
 ;死亡出生過程の場合
 :C戦略とD戦略をとる頂点の境界部分から2つ離れたところまでの合計4頂点を考慮する。
-D戦略を取る側は、C戦略と隣接する頂点が ''b''、そのまた隣は ''0'' になる。
+<math>
-C戦略を取る側は、D戦略と隣接する頂点が <math>b-2c</math>、そのまた隣は <math>2(b-c)</math>になる。
+\begin{matrix}
-従って <math>b/c > 2</math> の場合はC戦略が優位。
+\longleftrightarrow & \circledcirc & \longleftrightarrow & \circledcirc & \longleftrightarrow & \circledast & \longleftrightarrow & \circledast & \longleftrightarrow\\
 一般化すると、次数 ''k'' の格子であれば <math> b/c > k</math>の場合にC戦略が優位になる。

@@ Line 80: / Line 80: @@
 ほとんどの遺伝子の突然変異は、自然淘汰において有利でも不利でもないとする[http://www.nig.ac.jp/museum_080501/evolution/C/bunsi-02.html 中立進化説]は当時大きな反響を呼んだ。
-突然変異が完全に中立な場合、<math>\gamma = 1</math>　から <math>x_1 = 1/N</math> となる。
+突然変異が完全に中立な場合、<math>\gamma = 1</math>　となり左右に均等なランダムウォークになる。
 各個体の子孫がそれぞれ集団全体をカバーする可能性があり、各個体が均等な機会を持つから、これは当然の値ともいえる。
 さて、確率 ''m'' でタイプ B という突然変異が生じるとき、変異体 B の生じる個体数は ''mN'' になる。
@@ Line 88: / Line 89: @@
 ==ネットワーク上の出生死亡過程==
 モラン過程では A 個体と B 個体の個数のみを考え、個体間のネットワークという概念が無かった。
-ここでは ''N'' 個体が遷移行列 <math>{\mathbf P}</math> であらわされるネットワークを考えよう。
+言い方を変えると、モラン過程は完全グラフ (complete graph) 上の相互作用である。
 各頂点は状態 A または B をとり、単位時間にある頂点 ''i'' が隣接する頂点 ''j'' に確率 <math>p_{ij}</math> で自分の状態をコピーする。
-また、B は A に比べ <math>1/r</math> の割合で選ばれる確率が高いとする。ここで扱うのは 0 &le; ''r'' &le; 1 の場合である (B が次第に増える場合)。
+また、B は A に比べ <math>1/r</math> の割合で選ばれる確率が高いとする。ここで扱うのは 0 &le; ''r'' &le; 1 の場合である (B は次第に増える)。
 ===モラン過程と同等なネットワーク===
@@ Line 127: / Line 129: @@
 ===固定確率を低めるネットワーク===
-いかに優性な個体 B が生じても、固定確率が中立進化の場合に同じ <math>1/n</math> 以上にならないネットワークは簡単に構成できる。
+いかに優性な個体 B が生じても、固定確率が中立進化の場合に同じ <math>1/n</math> 以上になれないネットワークは簡単に構成できる。
 例えば既約なネットワークに根 (root) となる頂点を一つ付け足した場合を考えれば、根にあたる頂点に優性な変異 B が生じない限り固定されないので、固定確率が <math>1/n</math> となる。同じ理由で、根にあたる頂点が複数あるネットワークは決して固定されることがない。
@@ Line 135: / Line 137: @@
 結果から先に言うと、固定確率は <math>\textstyle x_i = \frac{1-r^{2i}}{1-r^{2n}}</math> であらわされる。
-星型の枝が非常に多い場合を考え、周囲の頂点には状態Bが ''m'' 個、状態Aが ''N'' &minus; ''m'' 個あると仮定しよう。
+星型の枝が非常に多い場合を考えよう。
 周囲の頂点で状態 B を増やすには、中央の頂点が状態 B の際に選択されねばならず、
 周囲の頂点で状態 A を増やすには、中央の頂点が状態 A の際に選択されねばならない。

@@ Line 95: / Line 95: @@
 初めに1個体であった B が全体に広がる確率がMoran過程と同じ <math>\textstyle \frac{1-r}{1-r^N}</math> であるための条件を考えよう。
 現在 ''m'' 頂点が状態 B、残りが状態 A と仮定する。
-B のほうが A より <math>1/r</math> 倍選択されやすい場合、''N'' 個の頂点のうち、状態Aのものが選択される確率は <math>m/r</math> だけ個体数が増えていることに等しいから <math>1 /(N-m + m/r)</math> となる。
+B のほうが A より <math>1/r</math> 倍選択されやすい場合、''N'' 個の頂点のうち、状態 A にある頂点が選択される確率は <math>m/r</math> だけ個体数が増えていることに等しいから <math>1 /(N-m + m/r)</math> となる。
-状態 B の頂点が選択される確率は<math>1/r(N-m+ m/r)</math>である。
+状態 B の頂点が選択される確率は<math>1/r(N-m+ m/r)</math>である。両者をあわせると
 頂点 ''i'' が状態Bのとき <math>v_i = 1</math>, 状態Aのとき <math>v_i = 0</math>と書こう。
@@ Line 120: / Line 121: @@
 個体 ''k'' ただ一つが B である特殊例 <math>v_k = 1,\ v_i = 0\, (\forall i \neq k)</math> を考えると <math>\textstyle \sum_j p_{jk} = \sum_j p_{kj} = 1</math> が必要条件となる。
 ただし右側の等号は、考えているネットワークがマルコフ連鎖であるため、頂点から出る辺確率の和が1であることから導かれる。
-これがすべての頂点について成立するため、定常分布での存在確率が全頂点において等しいときには（別の言葉でいうと、全頂点が対等な関係にある場合は）、Moran過程と同じプロセスになる。
+この条件がすべての頂点について成立する。したがって、定常分布での存在確率が全頂点において等しいときには（別の言葉でいうと、全頂点が対等な関係にある場合は）、Moran過程と同じプロセスになる。
 定常分布での存在確率が全頂点で等しくなるのは、接続関係が対称なネットワークだけに限らず、非対称な場合もありうる。　例えば一方向にのみ遷移する環状ネットワークは方向性を持つので非対称だがMoran過程と同等になる。

@@ Line 104: / Line 104: @@
 <math>\textstyle B_{m\rightarrow (m+1)} = \frac{1}{r} \frac{\sum_i\sum_j p_{ij} v_i (1-v_j)}{m/r + N - m} </math>
-同様に、B 個体が''m'' &minus; 1 に減少する確率は
+同様に、B 個体が''m'' &minus; 1 に減少する確率は、状態 A の頂点 ''i'' (<math> v_i = 0</math>) が選ばれて、隣接する状態 B の頂点 ''j'' (<math> v_j = 1</math>) を上書きすればよい。
 <math>\textstyle B_{m\rightarrow (m-1)} = \frac{\sum_i\sum_j p_{ij} (1-v_i) v_j}{m/r + N - m} </math>

@@ Line 112: / Line 112: @@
 <math>\textstyle \frac{B_{m\rightarrow (m-1)}}{B_{m\rightarrow (m+1)}} = r</math>
-が成立せねばならず
+が成立せねばならず、すべての ''i'', ''j'' について
 <math>\textstyle \sum_i\sum_j p_{ij} v_i (1-v_j) = \sum_i\sum_j p_{ij} (1-v_i) v_j</math>
-個体 ''k'' ただ一つが B である特殊例 <math>v_k = 1,\ v_i = 0\, (\forall i \neq k)</math> を考えると <math>\textstyle \sum_j p_{jk} = \sum_j p_{kj} = 1</math> となる。
+となる。
 ただし右側の等号は、考えているネットワークがマルコフ連鎖であるため、頂点から出る辺確率の和が1であることから導かれる。
-つまり、定常分布での存在確率が全頂点において等しいときには（別の言葉でいうと、全頂点が対等な関係にある場合は）、Moran過程と同じプロセスになる。
+これがすべての頂点について成立するため、定常分布での存在確率が全頂点において等しいときには（別の言葉でいうと、全頂点が対等な関係にある場合は）、Moran過程と同じプロセスになる。
 定常分布での存在確率が全頂点で等しくなるのは、接続関係が対称なネットワークだけに限らず、非対称な場合もありうる。　例えば一方向にのみ遷移する環状ネットワークは方向性を持つので非対称だがMoran過程と同等になる。