Aritalab:Lecture/NetworkBiology/Random Walk/Recurrence

From Metabolomics.JP
< Aritalab:Lecture | NetworkBiology | Random Walk(Difference between revisions)
Jump to: navigation, search
m (→‎再帰確率の母関数)
Line 4: Line 4:
 
===再帰確率と二項係数の関係===
 
===再帰確率と二項係数の関係===
  
−
原点から出発して 2''n'' ステップ後に再び原点に戻っている確率 ''f'' ( 2 ''n'' ) は、左右にちょうど ''n'' 回ずつ移動すればよいので
+
原点から出発して 2''n'' ステップ後に再び原点に戻っている確率 ''p'' ( 2 ''n'' ) は、左右にちょうど ''n'' 回ずつ移動すればよいので
  
−
<math> f(2n) = \frac{2n!}{n! n!} p^n q^n \ </math>
+
<math> p(2n) = \frac{2n!}{n! n!} p^n q^n \ </math>
  
−
になります。''f'' (0) = 1 です。これは原点に何回戻ってもよい確率なので、 2''n'' ステップ後に初めて原点に戻ってくる再帰確率を ''g'' ( 2 ''n'' ) と書くと、
+
になります。''p'' (0) = 1 です。これは原点に何回戻ってもよい確率なので、 2''n'' ステップ後に初めて原点に戻ってくる再帰確率を ''f'' ( 2 ''n'' ) と書くと、
  
 
<math>
 
<math>
 
\begin{align}
 
\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 \\
 
&+ \cdots \\
−
&+ g(2n - 2) f(2) + g(2n) \\
+
&+ f(2n - 2) p(2) + f(2n) \\
−
&= \sum^n_{m=1} g(2m) f(2n - 2m)
+
&= \sum^n_{m=1} f(2m) p(2n - 2m)
 
\end{align}
 
\end{align}
 
</math>
 
</math>
Line 25: Line 25:
 
<math>
 
<math>
 
\begin{align}
 
\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 \\
 
\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}
 
\end{align}
 
</math>
 
</math>
  
−
が求まり、二項係数 ''f'' ( 2 ''n'' ) を用いて ''g'' ( 2 ''n'' ) を書き下すことができます。
+
が求まり、二項係数 ''p'' ( 2 ''n'' ) を用いて ''f'' ( 2 ''n'' ) を書き下すことができます。
  
 
===再帰確率の母関数===
 
===再帰確率の母関数===
−
ここでは再帰確率を母関数を用いて求めてみます。 ''f'', ''g'' の母関数を考えます。 ''g'' は 2 ''n'' 回目で初めて原点に戻ることを意味する関数なので ''n'' = 1 からスタートするところに注意しましょう。この議論の一般形は[[Aritalab:Lecture/NetworkBiology/Markov_Chains/StationaryDistribution|マルコフ連鎖定常分布のページ]]にも記されています。
+
ここでは再帰確率を母関数を用いて求めてみます。 ''p'', ''f'' の母関数を考えます。 ''f'' は 2 ''n'' 回目で初めて原点に戻ることを意味する関数なので ''n'' = 1 からスタートするところに注意しましょう。この議論の一般形は[[Aritalab:Lecture/NetworkBiology/Markov_Chains/StationaryDistribution|マルコフ連鎖定常分布のページ]]にも記されています。
  
 
<math>
 
<math>
 
\begin{align}
 
\begin{align}
−
F(z) &= \sum^{\infty}_{n=0} f(2n) z^{2n} \\
+
P(z) &= \sum^{\infty}_{n=0} p(2n) z^{2n} \\
−
G(z) &= \sum^{\infty}_{n=1} g(2n) z^{2n}
+
F(z) &= \sum^{\infty}_{n=1} f(2n) z^{2n}
 
\end{align}
 
\end{align}
 
</math>
 
</math>
  
−
ここで ''f'' と ''g'' の関係式から
+
ここで ''p'' と ''f'' の関係式から
  
 
<math>
 
<math>
 
\begin{align}
 
\begin{align}
−
f(2n) &= \sum^n_{m=1} g(2m) f(2n - 2m)\\
+
p(2n) &= \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} & = \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]\\
+
\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}
 
\end{align}
 
</math>
 
</math>
Line 59: Line 59:
 
<math>
 
<math>
 
\begin{align}
 
\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
 
  \vdots \ &= \ \vdots
 
\end{align}
 
\end{align}
Line 70: Line 70:
 
<math>
 
<math>
 
\begin{align}
 
\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]\\
+
\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} g(2m)z^{2m} \sum^{\infty}_{n=m} f(2n - 2m) z^{2n-2m}\\
+
&= \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}
 
\end{align}
 
</math>
 
</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> 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>
−
F(s) = (1 - 4pqz^2)^{-1/2}\,</math>
+
P(s) = (1 - 4pqz^2)^{-1/2}\,</math>
  
 
これから
 
これから
  
 
<math>
 
<math>
−
G(s) = 1 - \frac{1}{F(s)} = 1 - \sqrt{1 - 4pqz^2}
+
F(s) = 1 - \frac{1}{P(s)} = 1 - \sqrt{1 - 4pqz^2}
 
</math>
 
</math>
  
Line 93: Line 93:
  
 
<math>
 
<math>
−
G(1) = 1 - (1 - 4pq)^{1/2} = 1 - |p-q|\,
+
F(1) = 1 - (1 - 4pq)^{1/2} = 1 - |p-q|\,
 
</math>
 
</math>
  
Line 120: Line 120:
  
  
−
となり、母関数を用いた <math>G(1)\,</math> の値と一致します。
+
となり、母関数を用いた <math>F(1)\,</math> の値と一致します。
  
  
Line 128: Line 128:
  
 
<math>
 
<math>
−
\sum^{\infty}_{n=0} 2n \cdot g(2n) = \Big[ \frac{d G(z)}{dz} \Big]_{z=1} =  
+
\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 136: Line 136:
 
===到達確率===
 
===到達確率===
  
−
原点から出発して ''n'' ステップ後に位置 ''k'' に初めて到達する確率 <math>g_k(n)\ </math> は、再帰確率と同様に求められます。ここでは一般性を失わずに ''k'' > 0 とし、 ''n'' と ''k'' の偶奇が一致する制約を無視して議論を進めます。まず ''n'' ステップ後に 位置 ''k'' にいる確率 <math>\,f_k(n)</math> から求めます。
+
原点から出発して ''n'' ステップ後に位置 ''k'' に初めて到達する確率 <math>f_k(n)\ </math> は、再帰確率と同様に求められます。ここでは一般性を失わずに ''k'' > 0 とし、 ''n'' と ''k'' の偶奇が一致する制約を無視して議論を進めます。まず ''n'' ステップ後に 位置 ''k'' にいる確率 <math>\ p_k(n)</math> から求めます。
  
−
<math> f_k(n) = \frac{n!}{((n+k)/2)! ((n-k)/2)!} p^{(n+k)/2} q^{(n-k)/2} \ </math>
+
<math> p_k(n) = \frac{n!}{((n+k)/2)! ((n-k)/2)!} p^{(n+k)/2} q^{(n-k)/2} \ </math>
  
−
再帰確率の場合と同じく、''n'' ステップ後に初めて ''k'' に到達する関数との関係を考えます。初めて ''k'' に到達したらそこを原点として残りのステップを関数 ''f'' で記述できるので以下のようになります。
+
再帰確率の場合と同じく、''n'' ステップ後に初めて ''k'' に到達する関数との関係を考えます。初めて ''k'' に到達したらそこを原点として残りのステップを関数 ''p'' で記述できるので以下のようになります。
  
−
<math>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)\, </math>
+
<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>g_k(k) = f_k(k) = p^k\,</math>
+
<math>f_k(k) = p_k(k) = p^k\,</math>
  
−
です。二項係数 <math>f_k( n ),\, f(n)</math> を用いて <math>g_k ( n )\,</math> を書き下すことができます。
+
です。二項係数 <math>p_k( n ),\, p(n)</math> を用いて <math>f_k ( n )\,</math> を書き下すことができます。
  
 
==== ''k'' = 1 の場合====
 
==== ''k'' = 1 の場合====
−
原点から出発して、 ''n'' ステップ目ではじめて ''k'' = 1 になる確率 <math>g_1 (n)\,</math> を考えます。
+
原点から出発して、 ''n'' ステップ目ではじめて ''k'' = 1 になる確率 <math>f_1 (n)\,</math> を考えます。
  
−
* ''n'' = 0 のとき、明らかに <math>g_1 (0) = 0\,</math>
+
* ''n'' = 0 のとき、明らかに <math>f_1 (0) = 0\,</math>
−
* ''n'' = 1 のとき、明らかに <math>g_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 g_1(m-1) g_1(n-m)\,</math> です。''m'' についての和を取ると
+
最初のステップは必ず左です。その後、 ''m'' - 1 回 ( ''m'' < ''n'' ) で右隣の原点に初めて戻り、さらに ''n'' - ''m'' 回で初めて位置 1 に到達します。その確率は <math> q f_1(m-1) f_1(n-m)\,</math> です。''m'' についての和を取ると
  
 
<math>
 
<math>
−
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))
+
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>
  
Line 166: Line 166:
 
<math>
 
<math>
 
\begin{align}
 
\begin{align}
−
g_1(2) &= q( g_1(1) g_1(0))\\
+
f_1(2) &= q( f_1(1) f_1(0))\\
−
g_1(3) &= q( g_1(1) g_1(1) + g_1(2) g_1(0))\\
+
f_1(3) &= q( f_1(1) f_1(1) + f_1(2) f_1(0))\\
−
g_1(4) &= q( g_1(1) g_1(2) + g_1(2) g_1(1) +  g_1(3) g_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 \\
−
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)) \\
+
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>G_1(z) = \sum^{\infty}_{n=0} g_1(n)z^n</math> を考慮しながら縦方向に足し合わせます。
+
母関数 <math>F_1(z) = \sum^{\infty}_{n=0} f_1(n)z^n</math> を考慮しながら縦方向に足し合わせます。
  
 
<math>
 
<math>
 
\begin{align}
 
\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\\
+
\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\\
−
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]\\
+
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]\\
−
G_1(z) - pz &= q z G_1(z)^2 \\  
+
F_1(z) - pz &= q z F_1(z)^2 \\  
 
\end{align}
 
\end{align}
 
</math>
 
</math>
  
−
この二次式を解くと <math> G_1(z) = \frac{1}{2qz}[1 - (1 - 4 pqz^2)^{1/2}]</math> となります。（もう一つの解は''z'' = 0 で発散する。）すなわち
+
この二次式を解くと <math> F_1(z) = \frac{1}{2qz}[1 - (1 - 4 pqz^2)^{1/2}]</math> となります。（もう一つの解は''z'' = 0 で発散する。）すなわち
  
 
<math>
 
<math>
 
\begin{align}
 
\begin{align}
−
G_1(1) &= \frac{1 - |p - q|}{2q} \\
+
F_1(1) &= \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 197: Line 197:
 
もし ''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 に到達します。
  
 +
<!---
 
;平均到達時間
 
;平均到達時間
  
 
<math>\sum^{\infty}_{n=0} n g_1(n) = \big[ \frac{d G_1(z)}{dz} \big]_{z=1}
 
<math>\sum^{\infty}_{n=0} n g_1(n) = \big[ \frac{d G_1(z)}{dz} \big]_{z=1}
 
</math>
 
</math>
 +
--->

Revision as of 09:57, 20 October 2011

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

Contents

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

原点から出発して 2n ステップ後に再び原点に戻っている確率 p ( 2 n ) は、左右にちょうど n 回ずつ移動すればよいので

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

になります。p (0) = 1 です。これは原点に何回戻ってもよい確率なので、 2n ステップ後に初めて原点に戻ってくる再帰確率を f ( 2 n ) と書くと、

\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 ( 2 n ) を用いて f ( 2 n ) を書き下すことができます。

再帰確率の母関数

ここでは再帰確率を母関数を用いて求めてみます。 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回原点に戻ってくる確率は r2 (1 − r )、ちょうど n 回原点に戻ってくる確率は rn (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 に到達します。


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

Variants
Actions
Navigation
metabolites
Toolbox