Aritalab:Lecture/NetworkBiology/Markov Chains

From Metabolomics.JP
Jump to: navigation, search
Wiki Top Up one level レポートの書き方 Arita Laboratory

Contents

ここではランダムウォークを考えるのに便利な概念を導入します。

マルコフ連鎖

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

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

を満たすときにマルコフ連鎖 (Markov chain) と呼ばれます。マルコフとはロシアの統計学者 Andrei A. Markov (1856-1922) のことで、マルコフ連鎖に関する多くの功績を残しました。状態 (state) X_t が状態 X_{t-1} のみに依存して決まる性質をマルコフ性 (Markov property) または無記憶性 (memoryless property) といいます。

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


{\mathbf P} = 
\begin{bmatrix}
  p_{11}  & p_{12} & \cdots & p_{1j} & \cdots \\
  p_{21}  & p_{22} & \cdots & p_{2j} & \cdots \\
  \vdots   & \vdots  & \ddots & \vdots  & \ddots \\ 
  p_{i1}  & p_{i2} & \cdots & p_{ij} & \cdots \\
  \vdots   & \vdots  & \ddots & \vdots  & \ddots \\ 
\end{bmatrix}

で記述できます。[1] 遷移確率を表すので行列の行方向に足し合わせた値は必ず 1 になっており、確率行列 (stochastic matrix) と呼ばれます。もし行方向に足し合わせても 1 になる場合、二重確率行列 (doubly stochastic matrix) と呼ばれます。

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

p_{ij}^{(m)} = \mbox{Prob}(X_{t+m} = j | X_{t} = i )

と書きましょう。右肩にある (m) という表記は、m ステップ後という意味で m 乗ではありません。1ステップ目で移動した先を k と書くと \textstyle p_{ij}^{(m)} = \sum_{k} p_{ik} \cdot p^{(m-1)}_{kj} であるから、遷移行列{\mathbf P}m 乗すれば正確に m ステップで移った先を示す遷移行列を得ます(数学的帰納法)。また記法をそろえるために

p_{ij}^{(1)} = p_{ij}

p_{ij}^{(0)} =
\begin{cases}\textstyle
1 & (j = i)\\
0 & (j \not= i)
\end{cases}

と定義します。

チャップマン-コルモゴロフの等式

m ステップの遷移を、 s ステップと ms ステップに分解する以下の式は、チャップマン-コルモゴロフの等式と呼ばれます[2]

p^{(m)}_{ij} = \textstyle\sum^{\infty}_{k=1} p^{(s)}_{ik} p^{(m-s)}_{kj} \quad (0 < s < m)

以下では p^{(m)}_{ij} \geq p^{(s)}_{ik} p^{(m-s)}_{kj} という等式をよく使います。マルコフ連鎖の主なテーマは、ネットワーク上を遷移行列に従って無限時間移動した際の、各状態における存在確率(定常分布)です。 ただしユニークな定常分布が存在するためには、これから述べる規約、再帰性、非周期性という概念が必要になります。

既約

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

  • 反射律 (reflexivity): いかなる状態 i も、i \leftrightarrow i
  • 対称律 (symmetry): i \leftrightarrow jならj \leftrightarrow i
  • 推移律 (transitivity): i \leftrightarrow jかつj \leftrightarrow kならi \leftrightarrow k

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

また、状態集合 C は、C に属すどの状態からも C 以外の状態に抜け出せないとき、閉じている (closed) といいます。例えば、グラフ表現した際に外に出る辺をもたない状態だけからなる集合は閉じています。

例: 1次元のウォーク

0 と N の間を左右に1ステップずつ移動し、0, N を吸収状態とするランダムウォークを考えます。0 から N までの状態は 3 つの同値類 {0}, {1, 2, ..., N−1}, {N} に分かれ、{0, N} は閉じています。

周期性

状態 i に戻ってくるまでのステップ数が自然数 k (>1) の倍数回に限られ、しかも k がこの性質を持つ最大公約数の場合、状態 i は周期 k でといいます。 k = 1 のとき、状態は非周期的であるといいます。マルコフ連鎖の中で同じ同値類に属する (communicativeな) 状態 i, j は同じ周期をもちます[3]

例:円周上のウォーク

円周上に配置された N 状態が一方向につながったマルコフ連鎖は、規約で周期 N を持ちます。遷移行列 P を N 乗すると、恒等行列 I になります。

再帰性

状態 i から出発し時刻 t になって初めて j に到達する確率をf^{(t)}_{ij}と書くことにします。 前出のp^{(t)}_{ij}は複数回 j を訪れることを許すため、f^{(t)}_{ij} \leq p^{(t)}_{ij}となります。

再帰時間

同じ状態に初めて戻る確率 f^{(t)}_{ii} を初再帰確率 (first return probability) と呼び、 f^{(0)}_{ii} = 0 と定義します。状態 i

\textstyle \sum_{t=1}^{\infty} f^{(t)}_{ii} < 1であれば一時的 (transient)
\textstyle \sum_{t=1}^{\infty} f^{(t)}_{ii} = 1であれば再帰的 (recurrent)

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

状態 i における平均初再帰時間 (mean first return time または mean recurrence time) を \mu_{ii} = \textstyle\sum^{\infty}_{t=1} tf^{(t)}_{ii} と書きます。状態 i が一時的な場合は \mu_{ii} = \infty です。

状態 i が再帰的でも \mu_{ii} が有限とは限りません。初再帰時間の期待値が有限なとき正再帰的 (positive recurrent)、そうでない場合をゼロ再帰的 (null recurrent) と呼びます。

例:2 × 2 行列

以下の確率行列を持つ 2 状態のマルコフ連鎖は正再帰的です。


{\mathbf P} = 
\begin{bmatrix}
  p_{11}  & p_{12} \\
  p_{21}  & p_{22} \\
\end{bmatrix}\quad 
0 < p_{ii} < 1 \ (i = 1,2)

直感的には 2 状態の間を行き来できるため、必ず戻ってきます[4]

例:ゼロ再帰的なマルコフ連鎖

正の整数値に対応するマルコフ連鎖を仮定し、状態 i から確率 i/(i + 1) で状態 i + 1 に、確率 1/(i + 1) で状態 1 に移動するとします。高い確率で無限遠に進んでいけるため、状態 1 に初めて戻るまでの期待値は無限大でゼロ再帰的です[5]

ゼロ再帰性を満たすには無限の状態数が必要です。

通過時間

状態 i から始めて j に最初に訪れる確率 f^{(t)}_{ij} を初通過確率 (first passage time probability) と呼び、 f^{(0)}_{ij} = 0 と定義します。平均初通過時間 (mean first passage time; MFPT) も同様に定義します。 \mu_{ij} = \textstyle\sum^{\infty}_{n=1} nf^{(n)}_{ij}

再帰時間の母関数

再帰時間と初再帰時間の間には以下の関係が成立します。


\begin{align}
p^{(n)}_{ii} &= f^{(0)}_{ii}p^{(n)}_{ii}
+ f^{(1)}_{ii}p^{(n-1)}_{ii} 
+ f^{(2)}_{ii}p^{(n-2)}_{ii} + ...
+ f^{(n)}_{ii}p^{(0)}_{ii} \\
&= 0 p^{(n)}_{ii}
+ f^{(1)}_{ii}p^{(n-1)}_{ii} 
+ f^{(2)}_{ii}p^{(n-2)}_{ii} + ...
+ f^{(n)}_{ii} 1 \\
&= \textstyle\sum^{n}_{k=1} f^{(k)}_{ii}p^{(n-k)}_{ii} 
\end{align}

初通過時間も同じです。


p^{(n)}_{ij} = \textstyle\sum^{n}_{k=1} f^{(k)}_{ij}p^{(n-k)}_{jj}

関数 fij と pij の母関数をそれぞれ Fij(s) と Pij(s) であらわします[6]


\begin{align}
F_{ij}(s) &= \textstyle\sum^{\infty}_{n=0} f^{(n)}_{ij}s^n \quad |s| < 1 \\
&= 0 s^0 + f^{(1)}_{ij} s + f^{(2)}_{ij} s^2 + f^{(3)}_{ij} s^3 ...\\
P_{ij}(s) &= \textstyle\sum^{\infty}_{n=0} p^{(n)}_{ij}s^n \quad |s| < 1 \\
&= 1 s^0 + p^{(1)}_{ij} s + p^{(2)}_{ij} s^2 + p^{(3)}_{ij} s^3 ...
\end{align}

(−1, 1) の間に収束する二つの数列の積はやはり(−1, 1) の間に収束することが知られています (Wade 2000)。


\begin{align}
F_{ii}(s) P_{ii}(s) &= \textstyle\sum^{\infty}_{r=1}\Big(\sum^{r}_{k=1}f^{(k)}_{ii}p^{(r-k)}_{ii}\Big) s^r \\
&= \textstyle\sum^{\infty}_{r=1} p^{(r)}_{ii} s^r \\
&= P_{ii}(s) - 1
\end{align}

Pii(s) から 1 を引くのは Fii(s) Pii(s) の第一項が f^{0}_{ii} p^{0}_{ii} = 0 であるのに対し Pii(s) の第一項は 1 になるからです。この関係から以下が導かれます。

\textstyle P_{ii}(s) = \frac{1}{1 - F_{ii}(s)}

同じようにして、通過時間の母関数に対して

F_{ij}P_{jj}(s) = P_{ij}(s) \quad (i \not= j)

が成立します。こちらは Pij(s) から 1 を引きません。これは Pij(s) の第一項が 1 でなく 0 であることに由来します。


状態数が N 個で有限の場合、少なくとも N+1 ステップ目には既に訪れた状態に辿り着きます。 よって少なくとも一つの再帰的な状態が存在しなくてはならず、そして再帰的な状態であれば、状態数が有限なので必ず正再帰的です。

例: 2次元ランダムウォーク

0 と N の間を左右に移動し、0, N を吸収状態とするランダムウォークを考えます。0, N は吸収状態とします。同値類 {1,2, ..., N−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 に対し、i から

\textstyle \sum^n_{j=0}\pi_i p_{i,j} = \sum^0{j=0}\pi_j p_{j, i} = \pi_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です。

参考・解説

  1. 状態 i から j への遷移確率を pij とする記法が主流ですが (Karlin & Taylor 1975)、Linda JS Allen (2011 2nd Ed) では j から i への遷移確率を pij と定義しています。そうすると定常分布を考える際に 以下で書くように行ベクトル π を用いて \bar\pi = \bar\pi \mathbf P とするのではなく、列ベクトルを用いて \bar\pi = \mathbf P \bar\pi と書けるようになります。記法上の問題であり、本質はかわりません。
  2. チャップマン-コルモゴロフの等式の証明
    
\begin{align}
p^{(m)}_{ij} & = \mbox{Prob}\{X_m = j | X_0 = i \} \\
& = \textstyle\sum^{\infty}_{k=1} \mbox{Prob}\{ X_m = j, X_s = k | X_0 = i \} \\
& = \textstyle\sum^{\infty}_{k=1} \mbox{Prob}\{ X_m = j | X_s = k, X_0 = i \} \mbox{Prob}\{ X_s = k | X_0 = i \}\\
& = \textstyle\sum^{\infty}_{k=1} \mbox{Prob}\{ X_m = j | X_s = k \} \mbox{Prob}\{ X_s = k | X_0 = i \} \\
& = \textstyle\sum^{\infty}_{k=1} p^{(m-s)}_{kj} p^{(s)}_{ik}
\end{align}
  3. 同じ同値類に属する状態の周期が等しいことの証明
    周期が 0 のときは自明。状態 i の周期が d(i) ≥ 1 と仮定します。状態 i から s ステップで i に戻る確率が 0 より大きくなる場合 (p^{(s)}_{ii} > 0) 、d(i) は s を割り切ります。 i と j が同値類に属する場合、 i → j を m ステップ、 j → i を n ステップで移動することが可能 (p^{(n)}_{ji} > 0, p^{(m)}_{ij} > 0) ですから p^{(n + ks + m)}_{jj} \geq; p^{(n)}_{ji} \{ p^{(s)}_{ii} p^{(s)}_{ii} ... p^{(s)}_{ii}\} p^{(m)}_{ij} > 0 となります。状態 j の周期は (n + ks + m) をどんな正の整数 k に対しても割り切るので、s も割り切ります。ここから d(j) ≤ d(i) が導かれます。同様の議論で d(i) ≤ d(j) も成り立つので d(i) = d(j) となります。
  4. 例:2 × 2 行列が正再帰的になることの証明
    確率行列は行方向の和が必ず 1 になるため、行列の要素は全て正の値をとります。一般に n ≥ 3 について f^{(n)}_{11} = p_{12}p^{n-2}_{22}p_{21} が成立します。状態 1 の再帰確率は 1 になります。状態 2 についても同じです。しかし平均初再帰時間は有限になります。 
\begin{align}
\textstyle\sum^{\infty}_{n=1}f^{(n)}_{11}
&= p_{11} + p_{12}p_{21}\textstyle\sum^{\infty}_{n=0}p^{n}_{22}\\
&= p_{11} + p_{12}p_{21}\textstyle\frac{1}{(1-p_{22})}
= p_{11} + p_{12} = 1\\
\mu_{11} &= \textstyle\sum^{\infty}_{n=1} n \cdot f^{(n)}_{11} = p_{11} + 2 (p_{12}p_{21}) + 3 (p_{12}p_{22}p_{21}) + 4 (p_{12}p_{22}^2p_{21}) + 5 ...\\
&= p_{11} + p_{12}p_{21} \textstyle\sum^{\infty}{n=0}(n+2)p_{22}^n\\
&= p_{11} + p_{12} + p_{12}p_{21} \textstyle\sum^{\infty}{n=0}(n+1)p_{22}^n\\
&= 1 + p_{12}p_{21}\frac{1}{(1 - p_{22})^2}\\
&= 1 + \frac{p_{12}}{p_{21}}
\end{align}
  5. ゼロ再帰性の証明
    状態 1 からスタートし最初の t ステップで 1 に戻らない確率は \textstyle \prod^t_{j=1} \frac{j}{j+1} = \frac{1}{t+1} \xrightarrow{t \rightarrow \infty} 0 したがって状態 1 は再帰的で \textstyle f^{(t)}_{11} = \frac{1}{t (t + 1)}t − 1 ステップ 1 に戻らず、t ステップ目で 1 に戻る)。しかし、状態 1 に初めて戻るまでの期待値は無限大。 \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
  6. fij と pijは一時的 (transient) かもしれないため総和は 1 以下の可能性があります。したがって確率母関数にはなっていません。
Personal tools
Namespaces

Variants
Actions
Navigation
metabolites
Toolbox