Aritalab:Lecture/NetworkBiology/Random Walk/Recurrence

Latest revision as of 00:06, 28 October 2011

[edit] 二項係数

左右に移動する確率がそれぞれ 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$ なので、有限の値に収束し、非再帰的（再帰不確実）です。

[edit] 二項係数と再帰確率

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

[edit] 再帰確率の母関数

ここでは再帰確率を母関数を用いて求めてみます。 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|\,$

になります。

[edit] 原点に戻る回数の期待値

再帰確率を 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)\,$ の値と一致します。

[edit] 平均再帰時間

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$

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

[edit] 到達確率

原点から出発して 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)}$ を書き下すことができます。

[edit] 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}$

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

$\begin{align} F_1(1) &= \textstyle\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 に到達します。

Aritalab:Lecture/NetworkBiology/Random Walk/Recurrence

Latest revision as of 00:06, 28 October 2011

Contents

[edit] 二項係数

[edit] 二項係数と再帰確率

[edit] 再帰確率の母関数

[edit] 原点に戻る回数の期待値

[edit] 平均再帰時間

[edit] 到達確率

[edit] k＝1 の場合

Personal tools

Namespaces

Variants

Views

Actions

Search

Navigation

metabolites

Toolbox

@@ Line 1: / Line 1: @@
-原点から出発したランダムウォークが原点に戻ってくる確率を再帰確率といいます。
+==二項係数==
-ここでは一次元ランダムウォークを考えます。
+左右に移動する確率がそれぞれ p, q のランダムウォークを考えます。原点から出発して 2n ステップ後に再び原点に戻っている確率 <math>p^{(2n)}_{0}</math> は、左右にちょうど n 回ずつ移動すればよいので
-===再帰確率と二項係数の関係===
+<math>\textstyle p^{(2n)}_{0} = \frac{2n!}{n! n!} p^n q^n \ </math>
-原点から出発して 2''n'' ステップ後に再び原点に戻っている確率 ''f'' ( 2 ''n'' ) は、左右にちょうど ''n'' 回ずつ移動すればよいので
+ここで p(0) = 1 です。スターリングの近似式 <math> n! \sim n^n e^{-n} \sqrt{2\pi n}</math> を使うと
-<math> f(2n) = \frac{2n!}{n! n!} p^n q^n \ </math>
+<math>\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}}
+</math>
-になります。''f'' (0) = 1 です。これは原点に何回戻ってもよい確率なので、 2''n'' ステップ後に初めて原点に戻ってくる再帰確率を ''g'' ( 2 ''n'' ) と書くと、
+となります。
+* p = q = 1/2 のとき 4pq = 1
+:<math>\textstyle\sum^{\infty}_{n=0} p^{(2n)}_{0} \sim \sum^{\infty}_{n=0} 1/\sqrt{\pi n} > (1/\sqrt{\pi}) \sum 1/n = \infty </math> なので原点には無限回戻ってくることになり、再帰確実です。
+* p &ne; 1/2 のとき 4pq < 1
+:<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> なので、有限の値に収束し、非再帰的（再帰不確実）です。
+==二項係数と再帰確率==
+原点から出発したランダムウォークが原点に戻ってくる確率を再帰確率といいます。
+n に原点に戻る確率を <math>p^{(2n)}</math>と書き、 2n ステップ後に初めて原点に戻ってくる確率を <math>f^{(2n)}</math> と書きましょう。
 <math>
 \begin{align}
-f(2n) &= g(2) f(2n - 2) \\
+p^{(2n)} &= f^{(2)} p^{(2n - 2)}\\
-&+ g(4) f(2n - 4) \\
+&+ f^{(4)} p^{(2n - 4)} \\
-&+ g(6) f(2n - 6) \\
+&+ f^{(6)} p^{(2n - 6)} \\
 &+ \cdots \\
-&+ g(2n - 2) f(2) + g(2n) \\
+&+ f^{(2n - 2)} p^{(2)} + f^{(2n)} \\
-&= \sum^n_{m=1} g(2m) f(2n - 2m)
+&= \textstyle\sum^n_{m=1} f^{(2m)} p^{(2n - 2m)}
 \end{align}
 </math>
@@ Line 25: / Line 37: @@
 <math>
 \begin{align}
-g(2) &= f(2)\\
+f^{(2)} &= p^{(2)}\\
-g(4) &= f(4) - f(2) g(2)\\
+f^{(4)} &= p^{(4)} - p^{(2)} f^{(2)}\\
-g(6) &= f(6) - f(4) g(2) - f(2) g(4) \\
+f^{(6)} &= p^{(6)} - p^{(4)} f^{(2)} - p^{(2)} f^{(4)} \\
 \cdots & \cdots \\
-g(2n) &= f(2n) - f(2n-2) g(2) - f(2n-4) g(4) - \cdots f(2) g(2n-2)
+f^{(2n)} &= p^{(2n)} - p^{(2n-2)} f^{(2)} - p^{(2n-4)} f^{(4)} - \cdots p^{(2)} f^{(2n-2)}
 \end{align}
 </math>
-が求まり、''f'' ( 2 ''n'' ) を用いて ''g'' ( 2 ''n'' ) を書き下すことができます。
+が求まり、二項係数 <math>p^{(2n)}</math> を用いて <math>f^{(2n)}</math> を書き下すことができます。
-===再帰確率の母関数===
+==再帰確率の母関数==
-ここでは再帰確率を母関数を用いて求めてみます。 ''f'', ''g'' の母関数を考えます。 ''g'' は 2 ''n'' 回目で初めて原点に戻ることを意味する関数なので ''n'' = 1 からスタートするところに注意しましょう。
+ここでは再帰確率を母関数を用いて求めてみます。 f は 2n 回目で初めて原点に戻ることを意味する関数なので n = 1 からスタートします。この議論の一般形は[[Aritalab:Lecture/NetworkBiology/Markov_Chains/StationaryDistribution|マルコフ連鎖定常分布のページ]]にも記されています。
 <math>
 \begin{align}
-F(z) &= \sum^{\infty}_{n=0} f(2n) z^{2n} \\
+P(z) &= \textstyle\sum^{\infty}_{n=0} p^{(2n)} z^{2n} \\
-G(z) &= \sum^{\infty}_{n=1} g(2n) z^{2n}
+F(z) &= \textstyle\sum^{\infty}_{n=1} f^{(2n)} z^{2n}
 \end{align}
 </math>
-ここで ''f'' と ''g'' の関係式から
+ここで p と f の関係式から
 <math>
 \begin{align}
-f(2n) &= \sum^n_{m=1} g(2m) f(2n - 2m)\\
+p^{(2n)} &= \textstyle\sum^n_{m=1} f^{(2m)} p^{(2n - 2m)}\\
-f(2n) z^{2n} & = \sum^n_{m=1} g(2m) z^{2m} f(2n - 2m) z^{2n-2m} \\
+p^{(2n)} z^{2n} & = \textstyle\sum^n_{m=1} f^{(2m)} z^{2m} p^{(2n - 2m)} z^{2n-2m} \\
-\sum^{\infty}_{n=1} f(2n) z^{2n} & = \sum^{\infty}_{n=1}\Big[ \sum^n_{m=1} g(2m) z^{2m} f(2n - 2m) z^{2n-2m} \Big]\\
+\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}
 </math>
@@ Line 59: / Line 72: @@
 <math>
 \begin{align}
-f(2) &= g(2)\\
+p^{(2)} &= f^{(2)}\\
-f(4) &= g(4) + g(2) f(2)\\
+p^{(4)} &= f^{(4)} + f^{(2)} p^{(2)}\\
-f(6) &= g(6) + g(4) f(2) + g(2) f(4)\\
+p^{(6)} &= f^{(6)} + f^{(4)} p^{(2)} + f^{(2)} p^{(4)}\\
   \vdots \ &= \ \vdots
 \end{align}
@@ Line 70: / Line 83: @@
 <math>
 \begin{align}
-\sum^{\infty}_{n=1} f(2n) z^{2n} &= \sum^{\infty}_{n=1}\Big[ \sum^n_{m=1} g(2m) z^{2m} f(2n - 2m) z^{2n-2m} \Big]\\
+\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]\\
-&= \sum^{\infty}_{m=1} g(2m)z^{2m} \sum^{\infty}_{n=m} f(2n - 2m) z^{2n-2m}\\
+&= \textstyle\sum^{\infty}_{m=1} f^{(2m)}z^{2m} \sum^{\infty}_{n=m} p^{(2n - 2m)} z^{2n-2m}\\
-&= G(z) F(z)
+&= F(z) P(z)
 \end{align}
 </math>
-左辺は <math>f(0) = 1\ </math> を含まないので　<math>F(s) - 1\ </math> となり、<math> G(z) = \frac{F(s) - 1}{F(s)}\ </math> となります。
+左辺は <math>p^{(0)} = 1\ </math> を含まないので　<math>P(s) - 1\ </math> となり、<math>\textstyle F(z) = \frac{P(s) - 1}{P(s)}\ </math> となります。
-無限級数 <math> F(s)\ </math> が発散するときは <math> G(z) \rightarrow 1 </math> となって再帰確実であり（必ず原点にもどる）、有限な値に収束するときは <math> G(z) < 1\ </math> で再帰不確実です。
+無限級数 <math> P(s)\ </math> が発散するときは <math> F(z) \rightarrow 1 </math> となって再帰確実であり（必ず原点にもどる）、有限な値に収束するときは <math> F(z) < 1\ </math> で再帰不確実です。
-実は、二項係数の母関数 <math>F(s) \ </math> は閉じた式に書き下すことができます。（[[Aritalab:Lecture/Basic/Generating_Function|母関数のページ]]を参照。）
+実は、二項係数の母関数 <math>P(s) \ </math> は閉じた式に書き下すことができます。（[[Aritalab:Lecture/Basic/Generating_Function|母関数のページ]]を参照。）
-<math>
+<math>\textstyle
-F(s) = (1 - 4pqz^2)^{-1/2}\,</math>
+P(s) = (1 - 4pqz^2)^{-1/2}</math>
 これから
 <math>
-G(s) = 1 - \frac{1}{F(s)} = 1 - \sqrt{1 - 4pqz^2}
+\textstyle F(s) = 1 - \frac{1}{P(s)} = 1 - \sqrt{1 - 4pqz^2}
 </math>
@@ Line 93: / Line 106: @@
 <math>
-G(1) = 1 - (1 - 4pq)^{1/2} = 1 - |p-q|\,
+\textstyle F(1) = 1 - (1 - 4pq)^{1/2} = 1 - |p-q|\,
 </math>
 になります。
-===原点に戻ってくる回数===
+==原点に戻る回数の期待値==
-再帰確率を ''r'' としましょう。ランダムウォークが原点に戻ってこない確率は (1 &minus; ''r'') です。いったん原点に戻ってきたら、ランダムウォークを再出発させると考えると、ちょうど1回原点に戻ってくる確率は ''r'' (1 &minus; ''r'' )、ちょうど2回原点に戻ってくる確率は ''r''<sup>2</sup> (1 &minus; ''r'' )、ちょうど ''n'' 回原点に戻ってくる確率は ''r''<sup>''n''</sup> (1 &minus; ''r'' ) になります。戻ってくる回数の期待値は
+再帰確率を r としましょう。ランダムウォークが原点に戻らない確率は (1 &minus; r) です。いったん原点に戻ったら、ランダムウォークを再出発させると考えると、ちょうど1回原点に戻る確率は r (1 &minus; r)、ちょうど2回原点に戻る確率は r<sup>2</sup> (1 &minus; r)、ちょうど n 回原点に戻る確率は r<sup>n</sup> (1 &minus; r) になります。戻る回数の期待値は
-<math>\sum^{\infty}_{n=0} n \cdot r^n (1-r) = \frac{r}{1-r}</math>
+<math>\textstyle\sum^{\infty}_{n=0} n \cdot r^n (1-r) = \frac{r}{1-r}</math>
-になります（この等式の導出は[[Aritalab:Lecture/Basic/Generating_Function|母関数]]のページを参照）。一方で、ランダムウォークが原点に戻ってくる回数は ''n'' ステップ後に原点にいる確率をすべて足し合わせたものにも等しいので
+になります（この等式の導出は[[Aritalab:Lecture/Basic/Generating_Function|母関数]]のページを参照）。一方で、ランダムウォークが原点に戻る回数は n ステップ後に原点にいる確率の総和にも等しいので
-<math>\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</math>
+<math>
+\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}
+</math>
 とも書けます（この等式の導出も[[Aritalab:Lecture/Basic/Generating_Function|母関数]]のページを参照）。
-両方の値を等しいとすることで、たとえば ''p'' > 1/2 と仮定して ''r'' / (1 &minus; ''r'')  = &minus;1 + 1 / (2 ''p'' &minus; 1) とおけば ''r'' = 2 ''q'' = 1 &minus; |''p'' &minus; ''q''| となり、母関数を用いた <math>G(1)\,</math> の値と一致します。
+両方の値は等しいので、たとえば ''p'' > 1/2 と仮定して
+<math>\textstyle\frac{r}{1-r} = \frac{1}{\sqrt{1 - 4pq}} - 1 \,</math>
+とおけば
+<math> r = 1 - | p - q | \,</math>
+となり、母関数を用いた <math>F(1)\,</math> の値と一致します。
+==平均再帰時間==
+p = q = 1/2 のときだけ再帰確実であり、平均再帰時間を考えられます。
+<math>
+\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
+</math>
+つまり、原点には必ず戻りますが無限時間かかる可能性があります。
+==到達確率==
+原点から出発して n ステップ後に位置 k に初めて到達する確率 <math>f_k^{(n)}</math> は、再帰確率と同様に求められます。ここでは一般性を失わずに k > 0 とし、 n と k の偶奇が一致する制約を無視して議論を進めます。まず n ステップ後に 位置 k にいる確率 <math>\ p_k^{(n)}</math> から求めます。
+<math>\textstyle p_k^{(n)} = \frac{n!}{((n+k)/2)! ((n-k)/2)!} p^{\frac{n+k}{2}} q^{\frac{n-k}{2}} </math>
+再帰確率の場合と同じく、n ステップ後に初めて k に到達する関数との関係を考えます。初めて k に到達したらそこを原点として残りのステップを関数 p で記述でき、以下になります。
+<math>\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)} </math>
+ここで
+<math>\textstyle f_k^{(k)} = p_k^{(k)} = p^k </math>
+です。二項係数 <math>p_k^{(n)}, p^{(n)}</math> を用いて <math>f_k^{(n)}</math> を書き下すことができます。
+=== k＝1 の場合===
+原点を出発し、 n ステップ目ではじめて k = 1 になる確率 <math>f_1^{(n)}</math> を考えます。
+* n = 0 のとき、明らかに <math>f_1^{(0)} = 0</math>
+* n = 1 のとき、明らかに <math>f_1^{(1)} = p</math>
+* n > 1 のとき
+最初のステップは必ず左です。その後、 m &minus; 1 回 ( m < n ) で右隣の原点に初めて戻り、さらに n &minus; m 回で初めて位置 1 に到達します。その確率は <math> q f_1^{(m-1)} f_1^{(n-m)}</math> です。m についての和を取ると
+<math>
+\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)})
+</math>
+これを n = 2 から並べましょう。
+<math>
+\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}
+</math>
+母関数 <math>\textstyle F_1(z) = \sum^{\infty}_{n=0} f_1^{(n)}z^n</math> を考慮しながら縦方向に足し合わせます。
+<math>
+\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}
+</math>
+この二次式を解くと <math>\textstyle F_1(z) = \frac{1}{2qz}[1 - (1 - 4 pqz^2)^{1/2}]</math> となります。（もう一つの解は z = 0 で発散する。）すなわち
+<math>
+\begin{align}
+F_1(1) &= \textstyle\frac{1 - |p - q|}{2q} \\
+&= p / q \quad (p < q)\\
+&= 1 \quad (p \geq q)
+\end{align}
+</math>
+もし p < q （左のほうに行く確率が高い）なら、永遠に待っていても <math>(q - p)/q\,</math> の確率で k = 1 に来ることはなく、p &ge; q の場合は必ず k = 1 に到達します。
+<!---
+;平均到達時間
+<math>\sum^{\infty}_{n=0} n g_1(n) = \big[ \frac{d G_1(z)}{dz} \big]_{z=1}
+</math>
+--->