Aritalab:Lecture/NetworkBiology/Random Walk/Recurrence

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

1次元ランダムウォーク

二項係数

左右に移動する確率がそれぞれ p, q のランダムウォークを考えます。原点から出発して 2n ステップ後に再び原点に戻っている確率 p (2n) は、左右にちょうど n 回ずつ移動すればよいので

$p(2n) = \frac{2n!}{n! n!} p^n q^n \$

になります。p (0) = 1 です。スターリングの近似式 $n! \sim n^n e^{-n} \sqrt{2\pi n}$ を使うと

$p(2n) = \frac{2n!}{n! n!} p^{n} q^{n} \sim \frac{(2n)^{2n}e^{-2n} \sqrt{4 \pi n}}{n^{2n} e^{-2n} 2\pi n } p^{n} q^{n} = \frac{(4pq)^n}{\sqrt{\pi n}}$

となります。

• p = q = 1/2 のとき 4pq = 1 となります。

$\textstyle\sum^{\infty}_{n=0} p(2n) \sim \sum^{\infty}_{n=0} 1/\sqrt{\pi n} > (1/\sqrt{\pi}) \sum 1/n = \infty$ なので原点には無限回戻ってくることになり、再帰確実です。

• p ≠ 1/2 のとき 4pq < 1 となります。

$\textstyle\sum^{\infty}_{n=0} p(2n) \sim (1/\sqrt{\pi})\sum^{\infty}_{n=0} (4pq)^n/\sqrt{n} \rightarrow N < \infty$ なので、有限の値に収束し、非再帰的になります。

二項係数と再帰確率

さきの p(2n) という関数は原点に何回戻ってもよい条件で 2n ステップ後に原点にいる確率なので、 2n ステップ後に初めて原点に戻ってくる再帰確率を f (2n) と書くと、

$\begin{align} p(2n) &= f(2) p(2n - 2) \\ &+ f(4) p(2n - 4) \\ &+ f(6) p(2n - 6) \\ &+ \cdots \\ &+ f(2n - 2) p(2) + f(2n) \\ &= \sum^n_{m=1} f(2m) p(2n - 2m) \end{align}$

となります。この関係式から

$\begin{align} f(2) &= p(2)\\ f(4) &= p(4) - p(2) f(2)\\ f(6) &= p(6) - p(4) f(2) - p(2) f(4) \\ \cdots & \cdots \\ f(2n) &= p(2n) - p(2n-2) f(2) - p(2n-4) f(4) - \cdots p(2) f(2n-2) \end{align}$

が求まり、二項係数 p(2n) を用いて f(2n) を書き下すことができます。

再帰確率の母関数

ここでは再帰確率を母関数を用いて求めてみます。 p, f の母関数を考えます。 f は 2 n 回目で初めて原点に戻ることを意味する関数なので n = 1 からスタートするところに注意しましょう。この議論の一般形はマルコフ連鎖定常分布のページにも記されています。

$\begin{align} P(z) &= \sum^{\infty}_{n=0} p(2n) z^{2n} \\ F(z) &= \sum^{\infty}_{n=1} f(2n) z^{2n} \end{align}$

ここで p と f の関係式から

$\begin{align} p(2n) &= \sum^n_{m=1} f(2m) p(2n - 2m)\\ p(2n) z^{2n} & = \sum^n_{m=1} f(2m) z^{2m} p(2n - 2m) z^{2n-2m} \\ \sum^{\infty}_{n=1} p(2n) z^{2n} & = \sum^{\infty}_{n=1}\Big[ \sum^n_{m=1} f(2m) z^{2m} p(2n - 2m) z^{2n-2m} \Big]\\ \end{align}$

さらに

$\begin{align} p(2) &= f(2)\\ p(4) &= f(4) + f(2) p(2)\\ p(6) &= f(6) + f(4) p(2) + f(2) p(4)\\ \vdots \ &= \ \vdots \end{align}$

という関係を縦方向に眺めることによって、右辺の2重和の順序を入れ替えます。

$\begin{align} \sum^{\infty}_{n=1} p(2n) z^{2n} &= \sum^{\infty}_{n=1}\Big[ \sum^n_{m=1} f(2m) z^{2m} p(2n - 2m) z^{2n-2m} \Big]\\ &= \sum^{\infty}_{m=1} f(2m)z^{2m} \sum^{\infty}_{n=m} p(2n - 2m) z^{2n-2m}\\ &= F(z) P(z) \end{align}$

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

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

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

これから

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

となり再帰確率は

$F(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 | \,$

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

平均再帰時間

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

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

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

到達確率

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

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

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

$p_k(n) = f_k(k)p(n-k) + f_k(k+2)p(n-k-2) + \cdots + f_k(n-2)p(2) + f_k(n)\,$

ここで

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

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

k = 1 の場合

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

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

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

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

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

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

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

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

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

$\begin{align} F_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 に到達します。