Aritalab:Lecture/NetworkBiology/Markov Chains
m (→既約) |
m |
||
Line 76: | Line 76: | ||
また、状態集合 C は、C に属すどの状態からも C 以外の状態に抜け出せないとき、閉じている (closed) といいます。例えば、グラフ表現した際に外に出る辺をもたない状態だけからなる集合は閉じています。 | また、状態集合 C は、C に属すどの状態からも C 以外の状態に抜け出せないとき、閉じている (closed) といいます。例えば、グラフ表現した際に外に出る辺をもたない状態だけからなる集合は閉じています。 | ||
− | ; | + | ;例: 2次元ランダムウォーク |
0 と N の間を左右に移動し、0, N を吸収状態とするランダムウォークを考えます。0, N は吸収状態とします。すると3つの同値類 {0}, {1, 2, ..., N−1}, {N} が存在し、{0, N} は閉じています。 | 0 と N の間を左右に移動し、0, N を吸収状態とするランダムウォークを考えます。0, N は吸収状態とします。すると3つの同値類 {0}, {1, 2, ..., N−1}, {N} が存在し、{0, N} は閉じています。 | ||
Line 86: | Line 86: | ||
: <math>\textstyle \sum_{t= 1}^{\infty} r^t_{i,i} < 1</math>であれば一時的 (transient) | : <math>\textstyle \sum_{t= 1}^{\infty} r^t_{i,i} < 1</math>であれば一時的 (transient) | ||
: <math>\textstyle \sum_{t= 1}^{\infty} r^t_{i,i} = 1</math>であれば再帰的 (recurrent) | : <math>\textstyle \sum_{t= 1}^{\infty} r^t_{i,i} = 1</math>であれば再帰的 (recurrent) | ||
− | + | と呼ぶ。全ての状態が再帰的であれば、マルコフ連鎖自体を再帰的と呼びます。 | |
− | 状態 ''i'' が再帰的であっても、再帰までのステップ数(再帰時間)の期待値 <math>M_{i,i}</math> | + | 状態 ''i'' が再帰的であっても、再帰までのステップ数(再帰時間)の期待値 <math>M_{i,i}</math> が有限とは限りません。 |
− | 例えば正の整数値に対応するマルコフ連鎖を仮定し、状態 ''i'' から確率 ''i''/(''i'' +1) で状態 ''i'' +1 に、確率 1/(''i'' +1) で状態 1 | + | 例えば正の整数値に対応するマルコフ連鎖を仮定し、状態 ''i'' から確率 ''i''/(''i'' +1) で状態 ''i'' +1 に、確率 1/(''i'' +1) で状態 1 に移動する系を考えます。 |
状態 1 からスタートして最初の ''t'' ステップで 1 に戻らない確率は | 状態 1 からスタートして最初の ''t'' ステップで 1 に戻らない確率は | ||
Line 99: | Line 99: | ||
<math>\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</math> | <math>\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</math> | ||
− | 再帰時間の期待値が有限な状態を正再帰的 (positive recurrent)、そうでない場合をゼロ再帰的 (null recurrent) | + | 再帰時間の期待値が有限な状態を正再帰的 (positive recurrent)、そうでない場合をゼロ再帰的 (null recurrent) と呼びます。 |
− | + | ゼロ再帰性を満たすには無限の状態数が必要です。 | |
− | 状態数が ''N'' 個で有限の場合、少なくとも ''N+1'' | + | 状態数が ''N'' 個で有限の場合、少なくとも ''N+1'' ステップ目には既に訪れた状態に辿り着きます。 |
− | + | よって少なくとも一つの再帰的な状態が存在しなくてはならず、そして再帰的な状態であれば、状態数が有限なので必ず正再帰的です。 | |
+ | |||
+ | ;例: 2次元ランダムウォーク | ||
+ | 0 と N の間を左右に移動し、0, N を吸収状態とするランダムウォークを考えます。0, N は吸収状態とします。同値類 {1,2, ..., N−1} は一時的な状態です。 | ||
===周期性=== | ===周期性=== | ||
− | 状態 ''i'' に戻ってくるまでのステップ数が自然数 ''k'' (>1) の倍数回に限られ、しかも ''k'' がこの性質を持つ最大値の場合、状態 ''i'' は周期 ''k'' | + | 状態 ''i'' に戻ってくるまでのステップ数が自然数 ''k'' (>1) の倍数回に限られ、しかも ''k'' がこの性質を持つ最大値の場合、状態 ''i'' は周期 ''k'' です。 |
− | ''k=1'' | + | ''k=1'' のとき、状態は非周期的であるといいます。 |
+ | |||
===エルゴード的=== | ===エルゴード的=== | ||
− | 全ての状態が非周期的で正再帰的なマルコフ連鎖を、エルゴード的 (ergodic) | + | 全ての状態が非周期的で正再帰的なマルコフ連鎖を、エルゴード的 (ergodic) であるといいます。有限で規約かつ非周期的なマルコフ連鎖はエルゴード的になります。なぜなら、規約という条件で少なくとも一つの再帰的な状態が存在するため、全ての状態が再帰的になる。さらに有限なため、すべての状態が正再帰的といえるからです。 |
===定常分布=== | ===定常分布=== | ||
Line 127: | Line 131: | ||
\lim_{t \rightarrow \infty} p^t_{i,i} = \frac{1}{M_{i,i}}</math> | \lim_{t \rightarrow \infty} p^t_{i,i} = \frac{1}{M_{i,i}}</math> | ||
− | + | さらに定常分布においては、各状態に入る確率と出る確率が等しいことにも注意します。 | |
つまり全ての状態 ''i, j'' に対し、''i'' から | つまり全ての状態 ''i, j'' に対し、''i'' から | ||
<math>\textstyle \sum^n_{j=0}\pi_i p_{i,j} = \sum^0{j=0}\pi_j p_{j, i} = \pi_i</math> | <math>\textstyle \sum^n_{j=0}\pi_i p_{i,j} = \sum^0{j=0}\pi_j p_{j, i} = \pi_i</math> | ||
− | + | 定常分布がただ一つに定まることを証明しましょう。 | |
− | 仮に定常分布が二つあるとして、もう一つの分布を <math>\bar\phi</math> | + | 仮に定常分布が二つあるとして、もう一つの分布を <math>\bar\phi</math> と書きます。 |
定常分布であるから | 定常分布であるから | ||
Line 139: | Line 143: | ||
\sum_k \phi_k \pi_i = \pi_i \sum_k \phi_k = \pi_i</math> | \sum_k \phi_k \pi_i = \pi_i \sum_k \phi_k = \pi_i</math> | ||
− | すなわち<math>\bar \phi = \bar \pi</math> | + | すなわち<math>\bar \phi = \bar \pi</math>です。 |
===参考=== | ===参考=== |
Revision as of 16:01, 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) しているといい、と書きます。連結性は同値類を形成します。
- 反射律 (reflexivity): いかなる状態 i も、
- 対称律 (symmetry): なら
- 推移律 (transitivity): かつなら
全ての状態が同じ同値類 (communication class) に属すとき、つまり全ての頂点が互いに連結なとき、マルコフ連鎖は既約 (irreducible) といいます。既約なマルコフ連鎖とは、グラフ表現すると強連結 (strongly connected) になっていて、任意の頂点から任意の頂点に移動できる場合に相当します。
また、状態集合 C は、C に属すどの状態からも C 以外の状態に抜け出せないとき、閉じている (closed) といいます。例えば、グラフ表現した際に外に出る辺をもたない状態だけからなる集合は閉じています。
- 例: 2次元ランダムウォーク
0 と N の間を左右に移動し、0, N を吸収状態とするランダムウォークを考えます。0, N は吸収状態とします。すると3つの同値類 {0}, {1, 2, ..., N−1}, {N} が存在し、{0, N} は閉じています。
再帰性
状態 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 ステップ目には既に訪れた状態に辿り着きます。 よって少なくとも一つの再帰的な状態が存在しなくてはならず、そして再帰的な状態であれば、状態数が有限なので必ず正再帰的です。
- 例: 2次元ランダムウォーク
0 と N の間を左右に移動し、0, N を吸収状態とするランダムウォークを考えます。0, N は吸収状態とします。同値類 {1,2, ..., 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 が無い場合、マルコフ連鎖は有限ではない。もし定常分布があるとしたら(ない可能性もある)
の解が存在しなくてはならない。前出の解から類推して
が答えになる。このとき α < β でないと定常分布は存在しない。
出生死亡過程
このページを参照。