Aritalab:Lecture/NetworkBiology/Random Walk/Recurrence

二項係数

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

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

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

$\textstyle p^{(2n)}_{0} = \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)}_{0} \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)}_{0} \sim (1/\sqrt{\pi})\sum^{\infty}_{n=0} (4pq)^n/\sqrt{n} \rightarrow N < \infty$ なので、有限の値に収束し、非再帰的（再帰不確実）です。

二項係数と再帰確率

原点から出発したランダムウォークが原点に戻ってくる確率を再帰確率といいます。 2n に原点に戻る確率を $p^{(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)} \\ &= \textstyle\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)}$ を書き下すことができます。

再帰確率の母関数

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

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

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

$\begin{align} p^{(2n)} &= \textstyle\sum^n_{m=1} f^{(2m)} p^{(2n - 2m)}\\ p^{(2n)} z^{2n} & = \textstyle\sum^n_{m=1} f^{(2m)} z^{2m} p^{(2n - 2m)} z^{2n-2m} \\ \textstyle\sum^{\infty}_{n=1} p^{(2n)} z^{2n} & = \textstyle\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} \textstyle\sum^{\infty}_{n=1} p^{(2n)} z^{2n} &= \textstyle\sum^{\infty}_{n=1}\Big[ \sum^n_{m=1} f^{(2m)} z^{2m} p^{(2n - 2m)} z^{2n-2m} \Big]\\ &= \textstyle\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\$ となり、 $\textstyle F(z) = \frac{P(s) - 1}{P(s)}\$ となります。無限級数 $P(s)\$ が発散するときは $F(z) \rightarrow 1$ となって再帰確実であり（必ず原点にもどる）、有限な値に収束するときは $F(z) < 1\$ で再帰不確実です。

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

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

これから

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

となり再帰確率は

$\textstyle 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) になります。戻る回数の期待値は

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

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

$\begin{align} \textstyle\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 \end{align}$

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

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

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

とおけば

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

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

平均再帰時間

p = q = 1/2 のときだけ再帰確実であり、平均再帰時間を考えられます。

$\textstyle\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)}$ から求めます。

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

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

$\textstyle 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)}$

ここで

$\textstyle 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 についての和を取ると

$\textstyle 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}$

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

$\begin{align} \textstyle\sum^{\infty}_{n=2} f_1^{(n)}z^n &= q \textstyle\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 \textstyle\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}$