Aritalab:Lecture/NetworkBiology/Random Walk/Recurrence
原点から出発したランダムウォークが原点に戻ってくる確率を再帰確率といいます。 ここでは一次元ランダムウォークを考えます。
再帰確率と二項係数の関係
原点から出発して 2n ステップ後に再び原点に戻っている確率 f ( 2 n ) は、左右にちょうど n 回ずつ移動すればよいので
になります。f (0) = 1 です。これは原点に何回戻ってもよい確率なので、 2n ステップ後に初めて原点に戻ってくる再帰確率を g ( 2 n ) と書くと、
となります。この関係式から
が求まり、f ( 2 n ) を用いて g ( 2 n ) を書き下すことができます。
再帰確率の母関数
ここでは再帰確率を母関数を用いて求めてみます。 f, g の母関数を考えます。 g は 2 n 回目で初めて原点に戻ることを意味する関数なので n = 1 からスタートするところに注意しましょう。
ここで f と g の関係式から
さらに
という関係を縦方向に眺めることによって、右辺の2重和の順序を入れ替えます。
左辺は を含まないので となり、 となります。 無限級数 が発散するときは となって再帰確実であり(必ず原点にもどる)、有限な値に収束するときは で再帰不確実です。
実は、二項係数の母関数 は閉じた式に書き下すことができます。(母関数のページを参照。)
これから
となり再帰確率は
になります。
原点に戻ってくる回数
再帰確率を r としましょう。ランダムウォークが原点に戻ってこない確率は (1 − r) です。いったん原点に戻ってきたら、ランダムウォークを再出発させると考えると、ちょうど1回原点に戻ってくる確率は r (1 − r )、ちょうど2回原点に戻ってくる確率は r2 (1 − r )、ちょうど n 回原点に戻ってくる確率は rn (1 − r ) になります。戻ってくる回数の期待値は
になります(この等式の導出は母関数のページを参照)。一方で、ランダムウォークが原点に戻ってくる回数は n ステップ後に原点にいる確率をすべて足し合わせたものにも等しいので
とも書けます(この等式の導出も母関数のページを参照)。
両方の値を等しいとすることで、たとえば p > 1/2 と仮定して
とおけば
となり、母関数を用いた の値と一致します。