Aritalab:Lecture/NetworkBiology/Markov Chains

Revision as of 10:52, 18 June 2010

マルコフ連鎖

グラフ上のランダムウォークを考えるのに便利な概念を導入する。

離散確率過程 $X_0, X_1, X_2 \ldots$ は

$\mbox{Pr}(X_t = a_t | X_{t-1} = a_{t-1}, X_{t-2} = a_{t-2}, \ldots X_0 = a_0 ) = \mbox{Pr}(X_t = a_t | X_{t-1} = a_{t-1})$

を満たすときにマルコフ連鎖 (Markov chain) と呼ばれる。状態 (state) $X_t$ が状態 $X_{t-1}$ のみに依存して決まる性質をマルコフ性 (Markov property) または無記憶性 (memoryless property) という。

マルコフ連鎖において状態 i から j への遷移確率を $p_{i,j} = \mbox{Pr}(X_t = j | X_{t-1} = i )$ と書けば、マルコフ連鎖は遷移行列

${\mathbf P} = \begin{bmatrix} p_{0,0} & p_{0,1} & \cdots & p_{0,j} & \cdots \\ p_{1,0} & p_{1,1} & \cdots & p_{1,j} & \cdots \\ \vdots & \vdots & \ddots & \vdots & \ddots \\ p_{i,0} & p_{i,1} & \cdots & p_{i,j} & \cdots \\ \vdots & \vdots & \ddots & \vdots & \ddots \\ \end{bmatrix}$

で記述できる。記法を拡張し、i から j へ正確に m ステップで移る遷移確率を

$p_{i,j}^m = \mbox{Pr}(X_{t+m} = j | X_{t} = i )$

と書こう。1ステップ目で移動した先を k と書くと $\textstyle p_{i,j}^m = \sum_{k} p_{i,k} p^{m-1}_{k,j}$ であるから、遷移行列 ${\mathbf P}$ を m 乗すれば正確に m ステップで移った先を示す遷移行列を得る（数学的帰納法）。

これから考えたいのは、ネットワーク上を遷移行列に従って無限時間移動した際の、各状態における存在確率（定常分布）である。ただし、ユニークな定常分布が存在するためにはこれから述べる規約、再帰性、非周期性という概念が必要になる。

既約

状態 i から j へ何ステップかで到達できる場合、j は i から到達可能 (accessible) と呼ぶ。互いに到達可能な状態 i, j どうしを連結 (communicate) しているといい、 $i \leftrightarrow j$ と書く。連結性は同値類を形成する。

反射律: いかなる状態 i も、 $i \leftrightarrow i$
対称律: $i \leftrightarrow j$ なら $j \leftrightarrow i$
推移律: $i \leftrightarrow j$ かつ $j \leftrightarrow k$ なら $i \leftrightarrow k$

全ての状態が同じ同値類に属すとき、つまり全ての頂点が互いに連結なとき、マルコフ連鎖は既約 (irreducible) という。既約なマルコフ連鎖は、グラフ表現すると強連結 (strongly connected) になっていて、任意の頂点から任意の頂点に移動できる。

再帰性

状態 i から出発し時刻 t になって初めて j に到達する確率を $r^t_{i,j}$ と書く。前出の $p^t_{i,j}$ は複数回 j を訪れることを許すため、 $r^t_{i,j} \leq p^t_{i,j}$ となることに注意しよう。

状態 i を

$\textstyle \sum_{t= 1}^{\infty} r^t_{i,i} < 1$ であれば一時的 (transient)

$\textstyle \sum_{t= 1}^{\infty} r^t_{i,i} = 1$ であれば再帰的 (recurrent)

と呼ぶ。全ての状態が再帰的であれば、マルコフ連鎖自体を再帰的と呼ぶ。

状態 i が再帰的であっても、再帰までのステップ数（再帰時間）の期待値 $M_{i,i}$ が有限とは限らない。例えば正の整数値に対応するマルコフ連鎖を仮定し、状態 i から確率 $i/(i+1)$ で状態 i+1 に、確率 $i/(i+1)$ で状態1に移動する系を考えよう。状態1からスタートして最初の t ステップで1に戻らない確率は

$\textstyle \prod^t_{j=1} \frac{j}{j+1} = \frac{1}{t+1} \xrightarrow{t \rightarrow \infty} 0$

したがって状態1は再帰的で、 $r^t_{1,1} = 1/t(t+1)$ 。しかし初めて状態1に戻ってくるまでのステップ数の期待値は

$\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$

再帰時間の期待値が有限な状態を正再帰的 (positive recurrent)、そうでない場合を零再帰的 (null recurrent) とよぶ。零再帰性を満たすには無限の状態数が必要になる。状態数が N 個で有限の場合、少なくとも N+1 ステップ目に既に訪れた状態に辿り着く。よって少なくとも一つの再帰的な状態が存在する。

周期性

状態 i に戻ってくるまでのステップ数が自然数 k (>1) の倍数回に限られ、しかも k がこの性質を持つ最大値の場合、状態 i は周期 k であるという。 k=1 のとき、状態は非周期的であるという。全ての状態が非周期的で正再帰的なマルコフ連鎖を、エルゴード的 (ergodic) であるという。

定常分布

マルコフ連鎖の遷移行列 $\mathbf P$ に対して

$\bar\pi = \bar\pi \mathbf P$

を満たし、要素の総和が1、つまり $\textstyle \sum_i \pi_i = 1$ となるような行ベクトル $\bar\pi = (\pi_0, \pi_1, \ldots, \pi_n)$ を定常分布 (stationary distribution) という。既約でエルゴード的なマルコフ連鎖は唯一つの定常分布 $\bar\pi$ を持ち、再帰時間の期待値との間に

$\textstyle \pi_i = \lim_{t\rightarrow \infty} p^t_{j,i} = \frac{1}{M_{i,i}}$

が成り立つ。これは再帰時間の期待値が出発する状態 j に依存しないことを意味し、再帰までのステップ数期待値が $M_{i,i}$ ならば状態 i に戻ってくる確率が $1/M_{i,i}$ であることに対応する。つまり各状態における存在確率は出発点に依存しない。

$\textstyle \lim_{t \rightarrow \infty} p^t_{j,i} = \lim_{t \rightarrow \infty} p^t_{i,i} = \frac{1}{M_{i,i}}$

さらに定常分布においては、各状態に入る確率と出る確率が等しいことにも注意する。全ての状態 i, j に対し

$\textstyle \pi_i p_{i,j} = \pi_j p_{j, i}$

定常分布がユニークに定まることを証明しよう。仮に定常分布が二つあるとして、もう一つの分布を $\bar\phi$ と書く。定常分布であるから

$\phi_i = \sum_k \phi_k p^t_{k,i} \xrightarrow{t \rightarrow \infty} \sum_k \phi_k \pi_i = \pi_i \sum_k \phi_k = \pi_i$

すなわち $\bar \phi = \bar \pi$ となる。

具体例

待ち行列

窓口に並ぶ客の人数 i をモデルしよう。単位時間において以下の事象が発生する。

もし i < n だったら、確率 $\alpha$ で客が一人増える。
もし i > 0なら、確率 $\beta$ で先頭から順に客は減る。
それ以外の場合、客の数は変化しない。

時刻 t における行列の長さを $X_t$ であらわす。すると以下の遷移確率を持つマルコフ連鎖で記述できる。

$\begin{align} p_{i, i+1} &= \alpha \quad \mbox{if} \quad i < n; \\ p_{i, i-1} &= \beta \quad \mbox{if} \quad i > 0; \\ p_{i, i} &= \begin{cases} 1 - \alpha & \mbox{if } \quad i=0,\\ 1 - \alpha - \beta & \mbox{if } \quad 1 \leq i \leq n - 1, \\ 1 - \beta & \mbox{if } \quad i = n \end{cases} \end{align}$

マルコフ連鎖は既約、有限、非周期的なので唯一の定常分布 $\bar \pi$ を持つ。満たすべき式は

$\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} \\ \pi_n &= \alpha \pi_{n-1} + (1-\beta)\pi_n \end{align}$

これを解くと $\pi_i = \pi_0 \Big( \frac{\alpha}{\beta} \Big)^i$ 。更に $\sum^n_{i=0} \pi_i = \pi_0 \sum^n_{i=0} \Big( \frac{\alpha}{\beta} \Big)^i = 1$ より

$\pi_i = \frac{ (\alpha/\beta)^i }{\sum^n_{i=0} (\alpha/\beta)^i}$

@@ Line 1: / Line 1: @@
 ==マルコフ連鎖==
-グラフ上のランダムウォークを考えよう。
+グラフ上のランダムウォークを考えるのに便利な概念を導入する。
 離散確率過程<math>X_0, X_1, X_2 \ldots</math>は
@@ Line 8: / Line 8: @@
 </math>
-を満たすときにマルコフ連鎖 (Markov chain) と呼ばれる。状態 <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>と書けば、マルコフ連鎖は遷移行列
@@ Line 30: / Line 30: @@
 <math>\textstyle p_{i,j}^m = \sum_{k} p_{i,k} p^{m-1}_{k,j} </math>
 であるから、遷移行列<math>{\mathbf P}</math>を ''m'' 乗すれば正確に ''m'' ステップで移った先を示す遷移行列を得る（数学的帰納法）。
+これから考えたいのは、ネットワーク上を遷移行列に従って無限時間移動した際の、各状態における存在確率（定常分布）である。
+ただし、ユニークな定常分布が存在するためにはこれから述べる規約、再帰性、非周期性という概念が必要になる。
 ===既約===
@@ Line 39: / Line 42: @@
 * 推移律: <math>i \leftrightarrow j</math>かつ<math>j \leftrightarrow k</math>なら<math>i \leftrightarrow k</math>
-全ての状態が同じ同値類に属すとき、つまり全ての頂点が互いに連結なとき、マルコフ連鎖は既約 (irreducible) という。既約なマルコフ連鎖をグラフ表現すると強連結 (strongly connected) になっていて、任意の頂点から任意の頂点に移動できる。
+全ての状態が同じ同値類に属すとき、つまり全ての頂点が互いに連結なとき、マルコフ連鎖は既約 (irreducible) という。既約なマルコフ連鎖は、グラフ表現すると強連結 (strongly connected) になっていて、任意の頂点から任意の頂点に移動できる。
 ===再帰性===
 状態 ''i'' から出発し時刻 ''t'' になって初めて ''j'' に到達する確率を<math>r^t_{i,j}</math>と書く。
-前出の<math>p^t_{i,j}</math>は複数回''j''を訪れることを許すため、<math>r^t_{i,j} \leq p^t_{i,j}</math>となることに注意しよう。
+前出の<math>p^t_{i,j}</math>は複数回 ''j'' を訪れることを許すため、<math>r^t_{i,j} \leq p^t_{i,j}</math>となることに注意しよう。
 状態 ''i'' を
@@ Line 67: / Line 70: @@
 ===周期性===
-状態 ''i'' に戻ってくるまでのステップ数が ''k >1'' の倍数回に限られ、しかも ''k'' がこの性質を持つ最大値の場合、状態 ''i'' は周期 ''k'' であるという。
+状態 ''i'' に戻ってくるまでのステップ数が自然数 ''k'' (>1) の倍数回に限られ、しかも ''k'' がこの性質を持つ最大値の場合、状態 ''i'' は周期 ''k'' であるという。
-''k=1'' であれば状態は非周期的であるという。
+''k=1'' のとき、状態は非周期的であるという。
-全ての状態が非周期的で正再帰的なマルコフ連鎖はエルゴード的 (ergodic) であるという。
+全ての状態が非周期的で正再帰的なマルコフ連鎖を、エルゴード的 (ergodic) であるという。
 ===定常分布===
@@ Line 77: / Line 80: @@
 を満たし、要素の総和が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> を持ち、 再帰時間の期待値との間に
 <math>\textstyle \pi_i = \lim_{t\rightarrow \infty} p^t_{j,i} = \frac{1}{M_{i,i}} </math>
 が成り立つ。
-これは再帰時間の期待値が出発する状態 ''j'' に依存しないことを意味し、再帰までのステップ数期待値が <math>M_{i,i}</math> ならば状態 ''i'' に戻ってくる確率が <math>1/M_{i,i}</math> であることに対応する。つまり
+これは再帰時間の期待値が出発する状態 ''j'' に依存しないことを意味し、再帰までのステップ数期待値が <math>M_{i,i}</math> ならば状態 ''i'' に戻ってくる確率が <math>1/M_{i,i}</math> であることに対応する。つまり各状態における存在確率は出発点に依存しない。
 <math>\textstyle \lim_{t \rightarrow \infty} p^t_{j,i} =
 \lim_{t \rightarrow \infty} p^t_{i,i} = \frac{1}{M_{i,i}}</math>
-さらに定常分布においては、各状態に入る確率と出る確率は等しいことにも注意する。全ての状態 ''i, j'' に対し
+さらに定常分布においては、各状態に入る確率と出る確率が等しいことにも注意する。
+全ての状態 ''i, j'' に対し
 <math>\textstyle \pi_i p_{i,j} = \pi_j p_{j, i} </math>
+定常分布がユニークに定まることを証明しよう。
 仮に定常分布が二つあるとして、もう一つの分布を <math>\bar\phi</math> と書く。
 定常分布であるから
@@ Line 137: / Line 142: @@
 <math> \pi_i = \frac{ (\alpha/\beta)^i }{\sum^n_{i=0} (\alpha/\beta)^i} </math>
-===出生死亡過程===
-====モラン過程====
-個体数を ''n'' とし、状態 ''i'' から ''i''+1, ''i''-1 の状態へそれぞれ確率<math>\alpha, \beta \ (\alpha + \beta < 1)</math>で遷移する場合を考える。
-また状態 0 と ''n'' は吸収状態とする。（従って定常分布は存在しない。）
-このマルコフ連鎖を1958年にモデルを発表した遺伝学者PAP MoranにちなんでMoran過程という。
-状態 ''i'' から出発して状態 ''n'' に到達する確率を <math>x_i</math> と書く。
-<math>
-\begin{align}
-x_0 &= 0 \\
-x_i &= \beta x_{i-1} + (1 - \alpha - \beta) x_i + \alpha x_{i+1} \quad (i = 1, \ldots N-1) \\
- &= x_i + \alpha (x_{i+1} - x_i) - \beta (x_i - x_{i-1}) \\
-x_n &= 1 \\
-\end{align}
-</math>
-ここで記法
-<math>
-\begin{align}
-y_i &= x_i - x_{i-1} \quad (i = 1, \ldots, N) \\
-\gamma &= \beta/\alpha
-\end{align}
-</math>
-を導入すると
-<math>\textstyle y_{i+1} = \gamma y_i, \quad \sum^n_{i=1} y_i = 1</math>
-を得る。
-<math> y_1 = x_1, \ y_2 = \gamma x_1, \ y_3 = \gamma^2 x_1, \cdots </math>
-を足し合わせると
-<math>
-x_1 = \frac{1}{1 + \sum^{n-1}_{j=1} \gamma^j} = \frac{1 - \gamma^n}{1 - \gamma}
-</math>
-これと
-<math>
-x_i = x_1 \Big( 1 + \sum^{i-1}_{j=1} \gamma^j \Big)
-</math>
-をあわせて
-<math>
-x_i = \frac{1 + \sum^{i-1}_{j=1} \gamma^j}{1 + \sum^{n-1}_{j=1} \gamma^j}
-=  \frac{1 - \gamma^i}{1 - \gamma^n}
-</math>
-''n'' 個体の集団において、全ての個体が最初タイプAであるとする。
-タイプBという突然変異が <math>\gamma < 1</math>を満たす、すなわちAよりも優位で個体数を増やす傾向にあるとする。
-このとき1個生じたタイプBが集団 ''n'' の中に固定される（集団全体をカバーする）確率は<math>x_1 \xrightarrow{n \rightarrow \infty} 1 - \gamma</math>。
-いかに優位な変異でも、必ず固定される訳ではない点に注意する。
-====木村の中立進化説====
-突然変異が完全に中立な場合、<math>\gamma = 1</math>　から <math>x_1 = 1/n</math>。
-確率 ''m'' でタイプBという突然変異が生じるとき、Bの生まれる個数は ''mn'' になるから、最初のBが生まれるまでの平均時間は <math>1/mn </math> である。
-結局、全てタイプAの集団が、全てタイプBの集団に進化する速度は、<math>mn/n = m</math> となり、集団のサイズに依存しない。ここから「分子時計」仮説が導かれる。

Aritalab:Lecture/NetworkBiology/Markov Chains

Revision as of 10:52, 18 June 2010

Contents

マルコフ連鎖

既約

再帰性

周期性

定常分布

具体例

待ち行列

Personal tools

Namespaces

Variants

Views

Actions

Search

Navigation

metabolites

Toolbox