Aritalab:Lecture/NetworkBiology/Random Walk/Recurrence

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

Latest revision as of 00:06, 28 October 2011

Contents

[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回原点に戻る確率は r2 (1 − r)、ちょうど n 回原点に戻る確率は rn (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 に到達します。


Retrieved from "http://metabolomics.jp/mediawiki/index.php?title=Aritalab:Lecture/NetworkBiology/Random_Walk/Recurrence&oldid=255257"
Personal tools
Namespaces

Variants
Actions
Navigation
metabolites
Toolbox