Aritalab:Lecture/NetworkBiology/Markov Chains
m |
m (→マルコフ連鎖) |
||
Line 10: | Line 10: | ||
</math> | </math> | ||
− | を満たすときにマルコフ連鎖 (Markov chain) | + | を満たすときにマルコフ連鎖 (Markov chain) と呼ばれます。マルコフとはロシアの統計学者 Andrei A. Markov (1856-1922) のことで、マルコフ連鎖に関する多くの功績を残しました。状態 (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> と書けば、マルコフ連鎖は遷移行列 | マルコフ連鎖において状態 ''i'' から ''j'' への遷移確率を<math>p_{i,j} = \mbox{Pr}(X_t = j | X_{t-1} = i )</math> と書けば、マルコフ連鎖は遷移行列 | ||
Line 25: | Line 25: | ||
</math> | </math> | ||
− | + | で記述できます。<ref>状態 i から j への遷移確率を p<sub>i,j</sub> とする記法が主流ですが (Karlin & Taylor 1975)、Linda JS Allen (2011 2nd Ed) では j から i への遷移確率を p<sub>i,j</sub> と定義しています。そうすると定常分布を考える際に 以下で書くように行ベクトル π を用いて <math>\bar\pi = \bar\pi \mathbf P</math> とするのではなく、列ベクトルを用いて <math>\bar\pi = \mathbf P \bar\pi </math> と書けるようになります。記法上の問題であり、本質はかわりません。</ref> | |
+ | 遷移確率を表すので行列の行方向に足し合わせた値は必ず 1 になっており、確率行列 (stochastic matrix) と呼ばれます。もし行方向に足し合わせても 1 になる場合、二重確率行列 (doubly stochastic matrix) と呼ばれます。 | ||
− | + | 記法を拡張し、''i'' から ''j'' へ正確に ''m'' ステップで移る遷移確率を | |
− | + | <math>p_{i,j}^m = \mbox{Prob}(X_{t+m} = j | X_{t} = i )</math> | |
+ | |||
+ | と書きましょう。1ステップ目で移動した先を ''k'' と書くと | ||
<math>\textstyle p_{i,j}^m = \sum_{k} p_{i,k} \cdot p^{m-1}_{k,j} </math> | <math>\textstyle p_{i,j}^m = \sum_{k} p_{i,k} \cdot p^{m-1}_{k,j} </math> | ||
− | であるから、遷移行列<math>{\mathbf P}</math>を ''m'' 乗すれば正確に ''m'' | + | であるから、遷移行列<math>{\mathbf P}</math>を ''m'' 乗すれば正確に ''m'' ステップで移った先を示す遷移行列を得ます(数学的帰納法)。また記法をそろえるために |
+ | |||
+ | <math>p_{i,j}^1 = p_{i,j}</math> | ||
+ | |||
+ | <math>p_{i,j}^0 = | ||
+ | \begin{cases}\textstyle | ||
+ | 1 & (j = i)\\ | ||
+ | 0 & (j \not= i) | ||
+ | \end{cases}</math> と定義します。 | ||
+ | |||
+ | ===チャップマン-コルモゴロフの等式=== | ||
+ | ''m'' ステップの遷移を、 ''s'' ステップと ''m'' − ''s'' ステップに分解する以下の式は、チャップマン-コルモゴロフの等式と呼ばれます。 | ||
+ | |||
+ | <math>p^m_{ij} = \sum^{\infty}_{k=1} p^{s}_{ik} p^{m-s}_{kj} \quad (0 < s < m)</math> | ||
+ | |||
+ | ;証明 | ||
+ | <math> | ||
+ | \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} | ||
+ | </math> | ||
− | + | これから考えたいのは、ネットワーク上を遷移行列に従って無限時間移動した際の、各状態における存在確率(定常分布)です。 | |
− | + | ただしユニークな定常分布が存在するためには、これから述べる規約、再帰性、非周期性という概念が必要になります。 | |
===既約=== | ===既約=== | ||
Line 83: | Line 111: | ||
<math>\bar\pi = \bar\pi \mathbf P</math> | <math>\bar\pi = \bar\pi \mathbf P</math> | ||
− | を満たし、要素の総和が 1 、つまり <math>\textstyle \sum_i \pi_i = 1</math> となるような行ベクトル<math>\bar\pi = (\pi_0, \pi_1, \ldots, \pi_n)</math>を定常分布 (stationary distribution) | + | を満たし、要素の総和が 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> | <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} = | <math>\textstyle \lim_{t \rightarrow \infty} p^t_{j,i} = | ||
Line 107: | Line 135: | ||
すなわち<math>\bar \phi = \bar \pi</math>となる。 | すなわち<math>\bar \phi = \bar \pi</math>となる。 | ||
+ | |||
+ | ===参考=== | ||
+ | <references/> | ||
==マルコフ連鎖の例== | ==マルコフ連鎖の例== |
Revision as of 15:44, 11 October 2011
Wiki Top | Up one level | レポートの書き方 | Arita Laboratory |
|
ここではランダムウォークを考えるのに便利な概念を導入します。
マルコフ連鎖
離散確率過程は
を満たすときにマルコフ連鎖 (Markov chain) と呼ばれます。マルコフとはロシアの統計学者 Andrei A. Markov (1856-1922) のことで、マルコフ連鎖に関する多くの功績を残しました。状態 (state) が状態 のみに依存して決まる性質をマルコフ性 (Markov property) または無記憶性 (memoryless property) といいます。
マルコフ連鎖において状態 i から j への遷移確率を と書けば、マルコフ連鎖は遷移行列
で記述できます。[1] 遷移確率を表すので行列の行方向に足し合わせた値は必ず 1 になっており、確率行列 (stochastic matrix) と呼ばれます。もし行方向に足し合わせても 1 になる場合、二重確率行列 (doubly stochastic matrix) と呼ばれます。
記法を拡張し、i から j へ正確に m ステップで移る遷移確率を
と書きましょう。1ステップ目で移動した先を k と書くと であるから、遷移行列を m 乗すれば正確に m ステップで移った先を示す遷移行列を得ます(数学的帰納法)。また記法をそろえるために
と定義します。
チャップマン-コルモゴロフの等式
m ステップの遷移を、 s ステップと m − s ステップに分解する以下の式は、チャップマン-コルモゴロフの等式と呼ばれます。
- 証明
これから考えたいのは、ネットワーク上を遷移行列に従って無限時間移動した際の、各状態における存在確率(定常分布)です。 ただしユニークな定常分布が存在するためには、これから述べる規約、再帰性、非周期性という概念が必要になります。
既約
状態 i から j へ何ステップかで到達できる場合、j は i から到達可能 (accessible) と呼ぶ。 互いに到達可能な状態 i, j どうしを連結 (communicate) しているといい、と書く。連結性は同値類を形成する。
- 反射律: いかなる状態 i も、
- 対称律: なら
- 推移律: かつなら
全ての状態が同じ同値類に属すとき、つまり全ての頂点が互いに連結なとき、マルコフ連鎖は既約 (irreducible) という。既約なマルコフ連鎖は、グラフ表現すると強連結 (strongly connected) になっていて、任意の頂点から任意の頂点に移動できる。
再帰性
状態 i から出発し時刻 t になって初めて j に到達する確率をと書く。 前出のは複数回 j を訪れることを許すため、となることに注意しよう。
状態 i を
- であれば一時的 (transient)
- であれば再帰的 (recurrent)
と呼ぶ。全ての状態が再帰的であれば、マルコフ連鎖自体を再帰的と呼ぶ。
状態 i が再帰的であっても、再帰までのステップ数(再帰時間)の期待値 が有限とは限らない。 例えば正の整数値に対応するマルコフ連鎖を仮定し、状態 i から確率 i/(i +1) で状態 i +1 に、確率 1/(i +1) で状態 1 に移動する系を考えよう。 状態 1 からスタートして最初の t ステップで 1 に戻らない確率は
したがって状態 1 は再帰的で、 = 1/t (t +1)。 しかし初めて状態 1 に戻ってくるまでのステップ数の期待値は
再帰時間の期待値が有限な状態を正再帰的 (positive recurrent)、そうでない場合をゼロ再帰的 (null recurrent) とよぶ。 ゼロ再帰性を満たすには無限の状態数が必要になる。 状態数が N 個で有限の場合、少なくとも N+1 ステップ目に既に訪れた状態に辿り着く。 よって少なくとも一つの再帰的な状態が存在しなくてはならない。そして再帰的な状態であれば、状態数が有限なので必ず正再帰的である。
周期性
状態 i に戻ってくるまでのステップ数が自然数 k (>1) の倍数回に限られ、しかも k がこの性質を持つ最大値の場合、状態 i は周期 k であるという。 k=1 のとき、状態は非周期的であるという。
エルゴード的
全ての状態が非周期的で正再帰的なマルコフ連鎖を、エルゴード的 (ergodic) であるという。有限で規約かつ非周期的なマルコフ連鎖はエルゴード的になる。なぜなら、規約という条件で少なくとも一つの再帰的な状態が存在するため、全ての状態が再帰的になる。さらに有限なため、すべての状態が正再帰的といえるからである。
定常分布
マルコフ連鎖の遷移行列に対して
を満たし、要素の総和が 1 、つまり となるような行ベクトルを定常分布 (stationary distribution) といいます。 既約でエルゴード的なマルコフ連鎖は唯一つの定常分布 を持ち、 再帰時間の期待値との間に
が成り立ちます。 これは再帰時間の期待値が出発する状態 j に依存しないことを意味し、再帰までのステップ数期待値が ならば状態 i に戻ってくる確率が であることに対応します。つまり各状態における存在確率は出発点に依存しません。
さらに定常分布においては、各状態に入る確率と出る確率が等しいことにも注意する。 つまり全ての状態 i, j に対し、i から
定常分布がただ一つに定まることを証明しよう。 仮に定常分布が二つあるとして、もう一つの分布を と書く。 定常分布であるから
すなわちとなる。
参考
- ↑ 状態 i から j への遷移確率を pi,j とする記法が主流ですが (Karlin & Taylor 1975)、Linda JS Allen (2011 2nd Ed) では j から i への遷移確率を pi,j と定義しています。そうすると定常分布を考える際に 以下で書くように行ベクトル π を用いて とするのではなく、列ベクトルを用いて と書けるようになります。記法上の問題であり、本質はかわりません。
マルコフ連鎖の例
待ち行列
窓口に並ぶ客の人数 i をモデルしよう。 単位時間において以下の事象が発生する。
- もし i < n だったら、確率 α で客が一人増える。
- もし i > 0 なら、確率 β で先頭から順に客は減る。
- それ以外の場合、客の数は変化しない。
時刻 t における行列の長さを考えると、有限のマルコフ連鎖になっている。遷移確率は以下のようになる。
マルコフ連鎖は既約、有限、非周期的なので唯一の定常分布 を持つ。 満たすべき式は
これを解くと 。 更に より
- 結論
- α > β のときは行列が長い確率の方が大きい
- α = β のとき、行列の長さは0からnまで等確率
同じ結果は、定常状態において α πi = β πi +1 という考察からも導くことができる。πi = (α/β) πi +1 から帰納法で πi = π0(α/β)i となる。
列の長さに上限 n が無い場合、マルコフ連鎖は有限ではない。もし定常分布があるとしたら(ない可能性もある)
の解が存在しなくてはならない。前出の解から類推して
が答えになる。このとき α < β でないと定常分布は存在しない。
出生死亡過程
このページを参照。