Aritalab:Lecture/NetworkBiology/Markov Chains

Wiki Top

Up one level

レポートの書き方

Arita Laboratory

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

マルコフ連鎖

離散確率過程$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 になっており、確率行列 (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 ステップと m − s ステップに分解する以下の式は、チャップマン-コルモゴロフの等式と呼ばれます。

$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 へ何ステップかで到達できる場合、j は i から到達可能 (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 は同じ周期をもちます。

例：円周上のウォーク

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

例： 1次元のウォーク

原点からスタートして左右に1ステップずつ移動するウォークでは、原点に戻るまでのステップ数が必ず偶数です。つまり、状態 0 は周期 2 になります。いずれの状態も周期は 2 です。

再帰性

状態 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)

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

平均初再帰時間 MFRT

状態 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 状態の間を自由に行き来できるため、必ず戻ってきます 。

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

正の整数値に対応するマルコフ連鎖を仮定し、状態 i から確率 i/(i + 1) で状態 i + 1 に、確率 1/(i + 1) で状態 1 に移動するとします。

${\mathbf P} = \begin{bmatrix} 1/2 & 1/2 & 0 & 0 & \cdots \\ 1/3 & 0 & 2/3 & 0 & \cdots \\ 1/4 & 0 & 0 & 3/4 & \cdots \\ 1/5 & 0 & 0 & 0 & \cdots \\ \vdots & \vdots & \vdots & \vdots \end{bmatrix}$

高い確率で無限遠に進んでいけるため、状態 1 に初めて戻るまでの期待値は無限大でゼロ再帰的です。

通過時間、平均初通過確率 MFPT

状態 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}$

定常分布

マルコフ連鎖の遷移行列$\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) といいます。定常分布は P^T の固有値 1 に対応する固有ベクトルともみなせます。状態数が有限の場合は 1 を必ず固有値に持つので定常分布が存在しますが、ただ一つに定まるとは限りません。

例：無限個の定常分布を持つマルコフ連鎖

確率行列が n 次元の単位行列 I のとき、定常状態は無限にあります。固有値 λ (n個) は全て 1 で、このマルコフ連鎖は既約ではありません (reducible)。

例：定常分布を持たないマルコフ連鎖

正の整数値に対応するマルコフ連鎖を仮定し、状態 i から i, i + 1, i + 2 ... にそれぞれ 1/2, 1/4, 1/8 ... の確率で遷移するとします。各状態が再帰不確実なため、定常状態 π はゼロベクトルになってしまいます。

${\mathbf P} = \begin{bmatrix} 1/2 & 1/4 & 1/8 & 1/16 & 1/32 & \cdots \\ 0 & 1/2 & 1/4 & 1/8 & 1/16 & \cdots \\ 0 & 0 & 1/2 & 1/4 & & 1/8 & \cdots \\ 0 & 0 & 0 & 1/2 & 1/4 & \cdots \\ \vdots & \vdots & \vdots & \vdots \end{bmatrix}$

定常分布をもつ条件

既約で、再帰確実かつ非周期的（エルゴード的）なマルコフ連鎖は唯一つの定常分布 $\bar\pi$ を持ち、 再帰時間の期待値との間に

$\textstyle \pi_i = \lim_{t\rightarrow \infty} p^{(t)}_{ji} = 1/\mu_{ii}$

が成り立ちます。この証明および関連する定理は、定常分布のページを参照してください。 これは再帰時間の期待値が出発する状態 j に依存しないことを意味し、再帰までのステップ数期待値が $\mu_{ii}$ ならば状態 i に戻ってくる確率が $1/\mu_{ii}$ であることに対応します。定常状態において、各状態での存在確率は出発点に依存しません。

$\textstyle \lim_{t \rightarrow \infty} p^{(t)}_{ji} = \lim_{t \rightarrow \infty} p^{(t)}_{ii} = 1/\mu_{ii}$

さらに定常分布においては、各状態に入る確率と出る確率が等しいことにも注意します。 つまり全ての状態 i, j に対し、i から出ていく確率の和は、i に入ってくる確率の和に等しく $\pi_i$ になります。

$\textstyle \sum^n_{j=0}\pi_i p_{ij} = \sum^n_{j=0}\pi_j p_{ji} = \pi_i$

エルゴード的であれば定常分布がただ一つに定まることを証明しましょう。 仮に定常分布が二つあるとして、もう一つの分布を $\bar\phi$ と書きます。 定常分布であるから

$\phi_i = \textstyle\sum_k \phi_k p^{(t)}_{ki} \xrightarrow{t \rightarrow \infty} \sum_k \phi_k \pi_i = \pi_i \sum_k \phi_k = \pi_i$

すなわち$\bar \phi = \bar \pi$です。