Aritalab:Lecture/NetworkBiology/Markov Chains

From Metabolomics.JP
< Aritalab:Lecture | NetworkBiology
Revision as of 02:33, 17 June 2010 by Adm (Talk | contribs)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

Contents

マルコフ連鎖

グラフ上のランダムウォークを考えよう。

離散確率過程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) と呼ばれる。状態 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 へ何ステップかで到達できる場合、ji から到達可能 (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}

出生死亡過程

モラン過程

個体数を n とし、状態 i から i+1, i-1 の状態へそれぞれ確率\alpha, \beta \ (\alpha + \beta < 1)で遷移する場合を考える。 また状態 0 と n は吸収状態とする。(従って定常分布は存在しない。) このマルコフ連鎖を1958年にモデルを発表した遺伝学者PAP MoranにちなんでMoran過程という。

状態 i から出発して状態 n に到達する確率を x_i と書く。


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

ここで記法


\begin{align}
y_i &= x_i - x_{i-1} \quad (i = 1, \ldots, N) \\
\gamma &= \beta/\alpha
\end{align}

を導入すると

\textstyle y_{i+1} = \gamma y_i, \quad \sum^n_{i=1} y_i = 1

を得る。

 y_1 = x_1, \ y_2 = \gamma x_1, \ y_3 = \gamma^2 x_1, \cdots

を足し合わせると


x_1 = \frac{1}{1 + \sum^{n-1}_{j=1} \gamma^j} = \frac{1 - \gamma^n}{1 - \gamma}

これと


x_i = x_1 \Big( 1 + \sum^{i-1}_{j=1} \gamma^j \Big)

をあわせて


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}

n 個体の集団において、全ての個体が最初タイプAであるとする。 タイプBという突然変異が \gamma < 1を満たす、すなわちAよりも優位で個体数を増やす傾向にあるとする。

このとき1個生じたタイプBが集団 n の中に固定される(集団全体をカバーする)確率はx_1 \xrightarrow{n \rightarrow \infty} 1 - \gamma。 いかに優位な変異でも、必ず固定される訳ではない点に注意する。

木村の中立進化説

突然変異が完全に中立な場合、\gamma = 1 から x_1 = 1/n。 確率 m でタイプBという突然変異が生じるとき、Bの生まれる個数は mn になるから、最初のBが生まれるまでの平均時間は 1/mn である。

結局、全てタイプAの集団が、全てタイプBの集団に進化する速度は、mn/n = m となり、集団のサイズに依存しない。ここから「分子時計」仮説が導かれる。

Personal tools
Namespaces

Variants
Actions
Navigation
metabolites
Toolbox