Aritalab:Lecture/NetworkBiology/Markov Chains
Wiki Top | Up one level | レポートの書き方 | Arita Laboratory |
|
マルコフ連鎖
グラフ上のランダムウォークを考えるのに便利な概念を導入する。
離散確率過程は
を満たすときにマルコフ連鎖 (Markov chain) と呼ばれる。状態 (state) が状態 のみに依存して決まる性質をマルコフ性 (Markov property) または無記憶性 (memoryless property) という。
マルコフ連鎖において状態 i から j への遷移確率をと書けば、マルコフ連鎖は遷移行列
で記述できる。記法を拡張し、i から j へ正確に m ステップで移る遷移確率を
と書こう。1ステップ目で移動した先を k と書くと であるから、遷移行列を m 乗すれば正確に m ステップで移った先を示す遷移行列を得る(数学的帰納法)。
これから考えたいのは、ネットワーク上を遷移行列に従って無限時間移動した際の、各状態における存在確率(定常分布)である。 ただし、ユニークな定常分布が存在するためにはこれから述べる規約、再帰性、非周期性という概念が必要になる。
既約
状態 i から j へ何ステップかで到達できる場合、j は i から到達可能 (accessible) と呼ぶ。 互いに到達可能な状態 i, j どうしを連結 (communicate) しているといい、と書く。連結性は同値類を形成する。
- 反射律: いかなる状態 i も、
- 対称律: なら
- 推移律: かつなら
全ての状態が同じ同値類に属すとき、つまり全ての頂点が互いに連結なとき、マルコフ連鎖は既約 (irreducible) という。既約なマルコフ連鎖は、グラフ表現すると強連結 (strongly connected) になっていて、任意の頂点から任意の頂点に移動できる。
再帰性
状態 i から出発し時刻 t になって初めて j に到達する確率をと書く。 前出のは複数回 j を訪れることを許すため、となることに注意しよう。
状態 i を
- であれば一時的 (transient)
- であれば再帰的 (recurrent)
と呼ぶ。全ての状態が再帰的であれば、マルコフ連鎖自体を再帰的と呼ぶ。
状態 i が再帰的であっても、再帰までのステップ数(再帰時間)の期待値 が有限とは限らない。 例えば正の整数値に対応するマルコフ連鎖を仮定し、状態 i から確率 で状態 i+1 に、確率 で状態1に移動する系を考えよう。 状態1からスタートして最初の t ステップで1に戻らない確率は
したがって状態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 < n だったら、確率 で客が一人増える。
- もし i > 0なら、確率 で先頭から順に客は減る。
- それ以外の場合、客の数は変化しない。
時刻 t における行列の長さを であらわす。すると以下の遷移確率を持つマルコフ連鎖で記述できる。
マルコフ連鎖は既約、有限、非周期的なので唯一の定常分布 を持つ。 満たすべき式は
これを解くと 。 更に より
出生死亡過程
このページを参照。