Aritalab:Lecture/NetworkBiology/Random Walk/Recurrence
m |
|||
Line 1: | Line 1: | ||
− | + | ==二項係数== | |
左右に移動する確率がそれぞれ p, q のランダムウォークを考えます。原点から出発して 2n ステップ後に再び原点に戻っている確率 <math>p^{(2n)}_{0}</math> は、左右にちょうど n 回ずつ移動すればよいので | 左右に移動する確率がそれぞれ p, q のランダムウォークを考えます。原点から出発して 2n ステップ後に再び原点に戻っている確率 <math>p^{(2n)}_{0}</math> は、左右にちょうど n 回ずつ移動すればよいので | ||
Line 18: | Line 18: | ||
:<math>\textstyle\sum^{\infty}_{n=0} p^{(2n)}_{0} \sim (1/\sqrt{\pi})\sum^{\infty}_{n=0} (4pq)^n/\sqrt{n} \rightarrow N < \infty</math> なので、有限の値に収束し、非再帰的(再帰不確実)です。 | :<math>\textstyle\sum^{\infty}_{n=0} p^{(2n)}_{0} \sim (1/\sqrt{\pi})\sum^{\infty}_{n=0} (4pq)^n/\sqrt{n} \rightarrow N < \infty</math> なので、有限の値に収束し、非再帰的(再帰不確実)です。 | ||
− | + | ==二項係数と再帰確率== | |
原点から出発したランダムウォークが原点に戻ってくる確率を再帰確率といいます。 | 原点から出発したランダムウォークが原点に戻ってくる確率を再帰確率といいます。 | ||
2n に原点に戻る確率を <math>p^{(2n)}</math>と書き、 2n ステップ後に初めて原点に戻ってくる確率を <math>f^{(2n)}</math> と書きましょう。 | 2n に原点に戻る確率を <math>p^{(2n)}</math>と書き、 2n ステップ後に初めて原点に戻ってくる確率を <math>f^{(2n)}</math> と書きましょう。 | ||
Line 47: | Line 47: | ||
が求まり、二項係数 <math>p^{(2n)}</math> を用いて <math>f^{(2n)}</math> を書き下すことができます。 | が求まり、二項係数 <math>p^{(2n)}</math> を用いて <math>f^{(2n)}</math> を書き下すことができます。 | ||
− | + | ==再帰確率の母関数== | |
ここでは再帰確率を母関数を用いて求めてみます。 f は 2n 回目で初めて原点に戻ることを意味する関数なので n = 1 からスタートします。この議論の一般形は[[Aritalab:Lecture/NetworkBiology/Markov_Chains/StationaryDistribution|マルコフ連鎖定常分布のページ]]にも記されています。 | ここでは再帰確率を母関数を用いて求めてみます。 f は 2n 回目で初めて原点に戻ることを意味する関数なので n = 1 からスタートします。この議論の一般形は[[Aritalab:Lecture/NetworkBiology/Markov_Chains/StationaryDistribution|マルコフ連鎖定常分布のページ]]にも記されています。 | ||
Line 111: | Line 111: | ||
になります。 | になります。 | ||
− | + | ==原点に戻る回数の期待値== | |
再帰確率を r としましょう。ランダムウォークが原点に戻らない確率は (1 − r) です。いったん原点に戻ったら、ランダムウォークを再出発させると考えると、ちょうど1回原点に戻る確率は r (1 − r)、ちょうど2回原点に戻る確率は r<sup>2</sup> (1 − r)、ちょうど n 回原点に戻る確率は r<sup>n</sup> (1 − r) になります。戻る回数の期待値は | 再帰確率を r としましょう。ランダムウォークが原点に戻らない確率は (1 − r) です。いったん原点に戻ったら、ランダムウォークを再出発させると考えると、ちょうど1回原点に戻る確率は r (1 − r)、ちょうど2回原点に戻る確率は r<sup>2</sup> (1 − r)、ちょうど n 回原点に戻る確率は r<sup>n</sup> (1 − r) になります。戻る回数の期待値は | ||
Line 139: | Line 139: | ||
となり、母関数を用いた <math>F(1)\,</math> の値と一致します。 | となり、母関数を用いた <math>F(1)\,</math> の値と一致します。 | ||
− | + | ==平均再帰時間== | |
p = q = 1/2 のときだけ再帰確実であり、平均再帰時間を考えられます。 | p = q = 1/2 のときだけ再帰確実であり、平均再帰時間を考えられます。 | ||
Line 150: | Line 150: | ||
つまり、原点には必ず戻りますが無限時間かかる可能性があります。 | つまり、原点には必ず戻りますが無限時間かかる可能性があります。 | ||
− | + | ==到達確率== | |
原点から出発して n ステップ後に位置 k に初めて到達する確率 <math>f_k^{(n)}</math> は、再帰確率と同様に求められます。ここでは一般性を失わずに k > 0 とし、 n と k の偶奇が一致する制約を無視して議論を進めます。まず n ステップ後に 位置 k にいる確率 <math>\ p_k^{(n)}</math> から求めます。 | 原点から出発して n ステップ後に位置 k に初めて到達する確率 <math>f_k^{(n)}</math> は、再帰確率と同様に求められます。ここでは一般性を失わずに k > 0 とし、 n と k の偶奇が一致する制約を無視して議論を進めます。まず n ステップ後に 位置 k にいる確率 <math>\ p_k^{(n)}</math> から求めます。 | ||
Line 166: | Line 166: | ||
です。二項係数 <math>p_k^{(n)}, p^{(n)}</math> を用いて <math>f_k^{(n)}</math> を書き下すことができます。 | です。二項係数 <math>p_k^{(n)}, p^{(n)}</math> を用いて <math>f_k^{(n)}</math> を書き下すことができます。 | ||
− | + | === k = 1 の場合=== | |
原点を出発し、 n ステップ目ではじめて k = 1 になる確率 <math>f_1^{(n)}</math> を考えます。 | 原点を出発し、 n ステップ目ではじめて k = 1 になる確率 <math>f_1^{(n)}</math> を考えます。 | ||
Revision as of 00:05, 28 October 2011
Contents |
二項係数
左右に移動する確率がそれぞれ p, q のランダムウォークを考えます。原点から出発して 2n ステップ後に再び原点に戻っている確率 は、左右にちょうど n 回ずつ移動すればよいので
ここで p(0) = 1 です。スターリングの近似式 を使うと
となります。
- p = q = 1/2 のとき 4pq = 1
- なので原点には無限回戻ってくることになり、再帰確実です。
- p ≠ 1/2 のとき 4pq < 1
- なので、有限の値に収束し、非再帰的(再帰不確実)です。
二項係数と再帰確率
原点から出発したランダムウォークが原点に戻ってくる確率を再帰確率といいます。 2n に原点に戻る確率を と書き、 2n ステップ後に初めて原点に戻ってくる確率を と書きましょう。
となります。この関係式から
が求まり、二項係数 を用いて を書き下すことができます。
再帰確率の母関数
ここでは再帰確率を母関数を用いて求めてみます。 f は 2n 回目で初めて原点に戻ることを意味する関数なので n = 1 からスタートします。この議論の一般形はマルコフ連鎖定常分布のページにも記されています。
ここで p と f の関係式から
さらに
という関係を縦方向に眺めることによって、右辺の2重和の順序を入れ替えます。
左辺は を含まないので となり、 となります。 無限級数 が発散するときは となって再帰確実であり(必ず原点にもどる)、有限な値に収束するときは で再帰不確実です。
実は、二項係数の母関数 は閉じた式に書き下すことができます。(母関数のページを参照。)
これから
となり再帰確率は
になります。
原点に戻る回数の期待値
再帰確率を r としましょう。ランダムウォークが原点に戻らない確率は (1 − r) です。いったん原点に戻ったら、ランダムウォークを再出発させると考えると、ちょうど1回原点に戻る確率は r (1 − r)、ちょうど2回原点に戻る確率は r2 (1 − r)、ちょうど n 回原点に戻る確率は rn (1 − r) になります。戻る回数の期待値は
になります(この等式の導出は母関数のページを参照)。一方で、ランダムウォークが原点に戻る回数は n ステップ後に原点にいる確率の総和にも等しいので
とも書けます(この等式の導出も母関数のページを参照)。
両方の値は等しいので、たとえば p > 1/2 と仮定して
とおけば
となり、母関数を用いた の値と一致します。
平均再帰時間
p = q = 1/2 のときだけ再帰確実であり、平均再帰時間を考えられます。
つまり、原点には必ず戻りますが無限時間かかる可能性があります。
到達確率
原点から出発して n ステップ後に位置 k に初めて到達する確率 は、再帰確率と同様に求められます。ここでは一般性を失わずに k > 0 とし、 n と k の偶奇が一致する制約を無視して議論を進めます。まず n ステップ後に 位置 k にいる確率 から求めます。
再帰確率の場合と同じく、n ステップ後に初めて k に到達する関数との関係を考えます。初めて k に到達したらそこを原点として残りのステップを関数 p で記述でき、以下になります。
ここで
です。二項係数 を用いて を書き下すことができます。
k = 1 の場合
原点を出発し、 n ステップ目ではじめて k = 1 になる確率 を考えます。
- n = 0 のとき、明らかに
- n = 1 のとき、明らかに
- n > 1 のとき
最初のステップは必ず左です。その後、 m − 1 回 ( m < n ) で右隣の原点に初めて戻り、さらに n − m 回で初めて位置 1 に到達します。その確率は です。m についての和を取ると
これを n = 2 から並べましょう。
母関数 を考慮しながら縦方向に足し合わせます。
この二次式を解くと となります。(もう一つの解は z = 0 で発散する。)すなわち
もし p < q (左のほうに行く確率が高い)なら、永遠に待っていても の確率で k = 1 に来ることはなく、p ≥ q の場合は必ず k = 1 に到達します。