Aritalab:Lecture/NetworkBiology/Random Walk/Recurrence

Revision as of 11:43, 4 July 2011

原点から出発したランダムウォークが原点に戻ってくる確率を再帰確率といいます。ここでは一次元ランダムウォークを考えます。

左辺は $f(0) = 1\$ を含まないので　 $F(s) - 1\$ となり、 $G(z) = \frac{F(s) - 1}{F(s)}\$ となります。無限級数 $F(s)\$ が発散するときは $G(z) \rightarrow 1$ となって再帰確実であり（必ず原点にもどる）、有限な値に収束するときは $G(z) < 1\$ で再帰不確実です。

実は、二項係数の母関数 $F(s) \$ は閉じた式に書き下すことができます。（母関数のページを参照。）

$F(s) = (1 - 4pqz^2)^{-1/2}\,$

これから

$G(s) = 1 - \frac{1}{F(s)} = 1 - \sqrt{1 - 4pqz^2}$

となり再帰確率は

$G(1) = 1 - (1 - 4pq)^{1/2} = 1 - |p-q|\,$

になります。

原点に戻ってくる回数

再帰確率を r としましょう。ランダムウォークが原点に戻ってこない確率は (1 − r) です。いったん原点に戻ってきたら、ランダムウォークを再出発させると考えると、ちょうど1回原点に戻ってくる確率は r (1 − r )、ちょうど2回原点に戻ってくる確率は r² (1 − r )、ちょうど n 回原点に戻ってくる確率は rⁿ (1 − r ) になります。戻ってくる回数の期待値は

$\sum^{\infty}_{n=0} n \cdot r^n (1-r) = \frac{r}{1-r}$

になります（この等式の導出は母関数のページを参照）。一方で、ランダムウォークが原点に戻ってくる回数は n ステップ後に原点にいる確率をすべて足し合わせたものにも等しいので

$\sum^{\infty}_{n=1} \binom{2n}{n} p^nq^n = \sum^{\infty}_{n=0} \binom{2n}{n} p^nq^n - 1 = F(1) - 1 = \frac{1}{\sqrt{1 - 4pq}} - 1 = \frac{1}{|2p - 1|} - 1$

とも書けます（この等式の導出も母関数のページを参照）。

両方の値を等しいとすることで、たとえば p > 1/2 と仮定して

$\frac{r}{1-r} = \frac{1}{\sqrt{1 - 4pq}} - 1 \,$

とおけば

$r = 1 - | p - q | \,$

となり、母関数を用いた $G(1)\,$ の値と一致します。

平均再帰時間

p = q = 1/2 のときだけ、再帰確実なので平均再帰時間を考えることができます。

$\sum^{\infty}_{n=0} 2n \cdot g(2n) = \Big[ \frac{d G(z)}{dz} \Big]_{z=1} = [ z(1 - z^2)^{-1/2} ]_{z=1} = \infty$

つまり、原点には必ず戻りますが無限時間かかる可能性があります。

到達確率

原点から出発して n ステップ後に位置 k に初めて到達する確率 $g_k(n)\$ は、再帰確率と同様に求められます。ここでは一般性を失わずに k > 0 とし、 n と k の偶奇が一致する制約を無視して議論を進めます。まず n ステップ後に位置 k にいる確率 $\,f_k(n)$ から求めます。

$f_k(n) = \frac{n!}{((n+k)/2)! ((n-k)/2)!} p^{(n+k)/2} q^{(n-k)/2} \$

再帰確率の場合と同じく、n ステップ後に初めて k に到達する関数との関係を考えます。初めて k に到達したらそこを原点として残りのステップを関数 f で記述できるので以下のようになります。

$f_k(n) = g_k(k)f(n-k) + g_k(k+2)f(n-k-2) + \cdots + g_k(n-2)f(2) + g_k(n)\,$

ここで

$g_k(k) = f_k(k) = p^k\,$

です。二項係数 $f_k( n ),\, f(n)$ を用いて $g_k ( n )\,$ を書き下すことができます。

k = 1 の場合

原点から出発して、 n ステップ目ではじめて k = 1 になる確率 $g_1 (n)\,$ を考えます。

n = 0 のとき、明らかに $g_1 (0) = 0\,$
n = 1 のとき、明らかに $g_1 (1) = p\,$
n > 1 のとき

最初のステップは必ず左です。その後、 m - 1 回 ( m < n ) で右隣の原点に初めて戻り、さらに n - m 回で初めて位置 1 に到達します。その確率は $q g_1(m-1) g_1(n-m)\,$ です。m についての和を取ると

$g_1(n) = q( g_1(1) g_1(n-2) + g_1(2) g_1(n-3) + \cdots + g_1(n-3) g_1(2) + g_1(n-2) g_1(1))$

これを n = 2 から並べましょう。

$\begin{align} g_1(2) &= q( g_1(1) g_1(0))\\ g_1(3) &= q( g_1(1) g_1(1) + g_1(2) g_1(0))\\ g_1(4) &= q( g_1(1) g_1(2) + g_1(2) g_1(1) + g_1(3) g_1(0))\\ \vdots \ &= \ \vdots \\ g_1(n) &= q( g_1(1) g_1(n-2) + g_1(2) g_1(n-3) + \cdots + g_1(n-3) g_1(2) + g_1(n-2) g_1(1) + g_1(n-1) g_1(0)) \\ \vdots \ &= \ \vdots \end{align}$

母関数 $G_1(z) = \sum^{\infty}_{n=0} g_1(n)z^n$ を考慮しながら縦方向に足し合わせます。

$\begin{align} \sum^{\infty}_{n=2} g_1(n)z^n &= q \sum^{\infty}_{n=2} \sum^{n-1}_{m=1} g_1(m)g_1(n-m-1) z^n\\ G_1(z) - pz &= q z \sum^{\infty}_{m=1}g_1(m) z^m \big[ \sum^{\infty}_{n=m+1} g_1(n-m-1) z^{n-m-1}\big]\\ G_1(z) - pz &= q z G_1(z)^2 \\ \end{align}$

この二次式を解くと $G_1(z) = \frac{1}{2qz}[1 - (1 - 4 pqz^2)^{1/2}]$ となります。（もう一つの解はz = 0 で発散する。）すなわち

$\begin{align} G_1(1) &= \frac{1 - |p - q|}{2q} \\ &= p / q \quad (p < q)\\ &= 1 \quad (p \geq q) \end{align}$

もし p < q （左のほうに行く確率が高い）なら、永遠に待っていても $(q - p)/q\,$ の確率で k = 1 に来ることはなく、p ≥ q の場合は必ず k = 1 に到達します。

平均到達時間

$\sum^{\infty}_{n=0} n g_1(n) = \big[ \frac{d G_1(z)}{dz} \big]_{z=1}$

@@ Line 153: / Line 153: @@
 原点から出発して、 ''n'' ステップ目ではじめて ''k'' = 1 になる確率 <math>g_1 (n)\,</math> を考えます。
-* ''n'' = 0 のとき、明らかに <math>g_1 (0) = 0\,</math>。
+* ''n'' = 0 のとき、明らかに <math>g_1 (0) = 0\,</math>
+* ''n'' = 1 のとき、明らかに <math>g_1 (1) = p\,</math>
-* ''n'' = 1 のとき、明らかに <math>g_1 (1) = p\,</math>。
 * ''n'' > 1 のとき
 最初のステップは必ず左です。その後、 ''m'' - 1 回 ( ''m'' < ''n'' ) で右隣の原点に初めて戻り、さらに ''n'' - ''m'' 回で初めて位置 1 に到達します。その確率は <math> q g_1(m-1) g_1(n-m)\,</math> です。''m'' についての和を取ると

Aritalab:Lecture/NetworkBiology/Random Walk/Recurrence

Revision as of 11:43, 4 July 2011

Contents

再帰確率と二項係数の関係

再帰確率の母関数

原点に戻ってくる回数

平均再帰時間

到達確率

k = 1 の場合

Personal tools

Namespaces

Variants

Views

Actions

Search

Navigation

metabolites

Toolbox