Aritalab:Lecture/NetworkBiology/Random Walk

Revision as of 09:58, 1 July 2011

1次元のランダムウォーク

原点から出発して1ステップ毎に確率 p で + 1, q (= 1 − p) で − 1 動くランダムウォークを考えましょう。 n ステップ後に、正の方向に k 回進んでいる確率は

$\binom{n}{k} p^k q^{(n-k)}\$

であらわされ、二項分布 (binomial distribution) B( n, p ) に従います。二項分布で正の方向に進むステップ数 k の期待値は np ^[1]なので、n ステップ後の位置の期待値は

$E[k - (n -k)] = E[2k - n] = 2 np - n = n(p - q) \$

になります。二項分布の分散は npq です^[2]。原点からの移動距離の 2 乗の期待値は

$E[(2 k - n)^2] = E[4k^2 - 4kn + n^2] = 4 n^2p^2 + 4pqn - 4 n^2p + n^2 = n^2 + 4 pqn (1-n) = 4pqn + (p-q)^2n^2\$

です。 p = q = 1/2 の場合、左右に同じ確率で広がるので位置の期待値は 0 となり。移動距離の期待値は n^1/2 になります。

まとめ

位置の期待値 $(p-q)n \$
移動距離の期待値 $\sqrt{(p-q)^2n^2 + 4pqn}$

拡散係数

ランダムウォークを時間の関数として捉えるため、τ 秒毎にステップを刻むことにして歩幅を δ cm とします。つまり、ステップ数 n = t / τ です。拡散の度合いは分散であらわされます。対称な二項分布の分散は n = (t/τ) δ² = 2 (δ² /2 τ) t となります（分散は距離の 2 乗平均なので δ が 2 乗されるところに注意）。拡散係数を D = δ² /2 τ (単位は cm²/sec) と書くと、分散は 2 Dt です。拡散に要する時間は、t = (距離)² / 2 D になります。水中の小分子なら D ∼ 10^{− 5} 、空気中の小分子なら D ∼ 10^{− 1} 程度であることが知られています。

考察

コーヒークリームがカップの中で広がったり、隣の人が香水をつけているかすぐ分かるのは、分子の拡散が原因ではなく水や空気の対流や攪拌のおかげです。拡散に必要な時間を計算してみましょう。

水中の小分子が拡散のみで x = 10^-4 cm = 1 μ m (大腸菌のサイズ) 進むのに必要な時間

t = x²/2D = 10^-8/(2 × 10^-5) = 5 × 10^-4　秒 (0.5 ミリ秒)

水中の小分子が拡散のみで x = 10 cm 進むのに必要な時間

t = x²/2D = (10)² /(2 × 10^-5) = 5 × 10⁶ 秒 = 2 ヶ月

空気中の小分子が拡散のみで x = 1 m 進むのに必要な時間

t = x²/2D = (100)² / (2 × 10^-1) = 5 × 10⁴ 秒 = 14 時間

再帰確率

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

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

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

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

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

となります^[3]。ここで f, g の母関数を考えます。 g は 2 n 回目で初めて原点に戻ることを意味する関数なので n = 1 からスタートするところに注意しましょう。

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

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

$\begin{align} f(2n) &= \sum^n_{m=1} g(2m) f(2n - 2m)\\ f(2n) z^{2n} & = \sum^n_{m=1} g(2m) z^{2m} f(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]\\ \end{align}$

さらに

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

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

$\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}_{m=1} g(2m)z^{2m} \sum^{\infty}_{n=m} f(2n - 2m) z^{2n-2m}\\ &= G(z) F(z) \end{align}$

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

^[4]。

再帰的な場合、つまり p = q = 1/2 であれば、戻るまでの期待時間を考えることは意味があります。これを平均再帰時間といい n ステップ後にはじめて原点に戻ってくる確率に n をかけて和をとると求まります。一次元のランダムウォークでも平均再帰時間は無限大になります。

考察: 公正なコインによる賭けでは、どんなに負けていても賭けを継続していれば収支は必ず 0 に戻せる（再帰性）。

ギャンブラーの破産問題

二人のプレーヤーがコインを k₁ と k₂ 枚ずつ持っています。確率 1/2 で勝てばコインを 1 枚うけとり、負ければ 1 枚渡します。勝負は原点から出発して左右に 1/2 の確率で移動するランダムウォークに相当し、時刻 t における位置はプレーヤー 1 が得たコインの枚数（勝ち数）です。状態 − k₁ になったらプレーヤー 1 が破産してゲームは終了し、k₂ になったらプレーヤー 2 が破産してゲームは終了します。このゲームは、状態 k₁ と k₂ が吸収状態になっているマルコフ連鎖とみなせます。プレーヤー 1 が破産する前に k₂ 枚のコインを獲得する確率 q を求めましょう。

時刻 t において位置が i にいる確率を $P^t_{i}$ と書きましょう。すると

$\textstyle \lim_{t\rightarrow \infty} P^t_{-k_1} = 1-q,\ \lim_{t\rightarrow \infty} P^t_{k_2} = q,\ \lim_{t\rightarrow \infty} P^t_{i} = 0 \ (-k_1 < i < k_2)$

となります。また、ゲームは公正なため、何回目の勝負であってもプレーヤー 1 が持つコイン数の期待値は 0 です。つまり時刻 t について数学的帰納法を用いると、常に

$\textstyle \sum^{k_2}_{i = -k_1} i P^t_{i} = 0 \ (t = 0, 1, \cdots)$

です。極限を取ると

$\textstyle \lim_{t\rightarrow \infty} \sum^{k_2}_{i = -k_1} i P^t_{i} = k_2 q - k_1 (1-q) = 0$

となるので $q = k_1 / (k_1 + k_2)$ です。つまりゲームに勝つ確率は、開始時の持ち点に比例します。

考察: 公正なコインを用いた賭けでも、資金が少ないギャンブラーが資金の多い胴元に勝つ見込みは少ない。

有限グラフ上のランダムウォーク

グラフ G( V , E ) の各頂点 u から出る辺を等確率 $1/d(u)$ で選んで動くグラフ上のランダムウォークを考えましょう。非周期性を仮定したいので、ここでは二部グラフでない連結なものだけを考慮します。すると、グラフの全頂点をまわるのに必要なランダムウォークの平均ステップ数は 4|V| · |E| 以下であることを示せます。

[定理] 頂点 u から v に到達するステップ数の期待値を $h_{u,v}$ と記述すると $\textstyle h_{u,u} = \frac{2|E|}{d(u)}$ が成立する。

証明

まずランダムウォークの定常分布 $\bar \pi$ が各頂点 v　において $\pi_v = \textstyle \frac{d(v)}{2|E|}$ であると仮定してみましょう。各頂点上の確率 $\pi_v$ の総和をとると $\textstyle \sum_{v \in V} \pi_v = \sum_{v \in V} \frac{d(v)}{2 |E|} = 1$ 。

また Failed to parse (lexing error): \textstyle \bar \pi {\mathbf P}　 = \sum_{u \in adj(v)} \pi_u \frac{1}{d(u)} = \sum_{u \in adj(v)} \frac{1}{2 |E|} = \frac{d(v)}{2|E|} = \bar \pi 　から、 $\textstyle \frac{d(v)}{2|E|}$ 　は定常分布の条件を満たしています。

各頂点への再帰時間の期待値は $\textstyle 1/\pi_u$ になるので、証明は終わりです。

[補題] 隣り合う頂点間のステップ数の期待値の上限は $2 |E|$ で抑えられる。

証明

各頂点への再帰時間の期待値を、二通りに計算してみます。 $\textstyle h_{u,u} = \frac{2 |E|}{ d(u) } = \frac{1}{d(u)} \sum_{v \in adj(u)} (1+ h_{v,u})$

つまり $\textstyle 2 |E| = \sum_{v \in adj(u)} (1+ h_{v,u})$ ですから $2 |E| > h_{v,u}$ です。

[補題] グラフ全体を訪れるのに必要な期待値の上限は $4 |V| |E|$ で抑えられる。

証明

与えられたグラフ全体をスパンする木を作ります。その上を全点辿ったときの辺数は $(2|V|-2)$ です。

$\textstyle \sum_1^{2|V|-2} h_{u,v} = (2|V|-2) \cdot 2|E| < 4|V|\cdot |E|$

このように、ある頂点から出発したランダムウォークが全ての頂点を訪れるまでの期待ステップ数をグラフの被覆時間 (cover time) と呼びます。

参考：式の導出

本文中に出てくる式の導出です。

↑ 期待値の定義に従って計算します。
$\begin{align} E[X] &= \sum_{k=0}^n k \binom{n}{k} p^k(1-p)^{n-k} = \sum_{k=1}^n k \binom{n}{k} p^k(1-p)^{n-k}\\ &= \sum_{k=1}^n k \frac{n}{k} \binom{n-1}{k-1} p^k(1-p)^{n-k} = \sum_{k=1}^n k \cdot \frac{n}{k} \cdot p \binom{n-1}{k-1} p^{k-1}(1-p)^{n-k}\\ &= np \sum^{n}_{k=1} \binom{n-1}{k-1} p^{k-1}(1-p)^{n-k} = np \end{align}$
↑ 分散の定義に従って計算します。まず
$\begin{align} E[X^2] &= k^2 \sum_{k=0}^n k \binom{n}{k} p^k(1-p)^{n-k} = \sum_{k=0}^n {k(k-1)+k} \binom{n}{k} p^k(1-p)^{n-k}\\ &= \sum_{k=0}^n k(k-1) \binom{n}{k} p^k(1-p)^{n-k} + \sum_{k=0}^n k \binom{n}{k} p^k(1-p)^{n-k}\\ &= \sum_{k=0}^n k(k-1) \binom{n}{k} p^k(1-p)^{n-k} + np \\ &= n(n-1) \sum_{k=2}^n k(k-1) \binom{n-2}{k-2} p^{k-2}(1-p)^{n-k} + np \\ &= n(n-1) p^2 + np \end{align}$
したがって
$\begin{align} V[X] &= E[X^2] - (E[X])^2 = n(n-1) p^2 + np - n^2p^2\\ &= np (1-p) \end{align}$
↑ この関係式から $\begin{align} g(2) &= f(2)\\ g(4) &= f(4) - f(2) g(2)\\ g(6) &= f(6) - f(4) g(2) - f(2) g(4) \\ \cdots & \cdots \\ g(2n) &= f(2n) - f(2n-2) g(2) - f(2n-4) g(4) - \cdots f(2) g(2n-2) \end{align}$ が求まり、f ( 2 n ) を用いて g ( 2 n ) を書き下すことができます。
↑ 再帰確率を 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 ステップ後に原点にいる確率をすべて足し合わせたものに等しいので $\textstyle \sum^{\infty}_{n=1} \binom{2n}{n} p^nq^n = \sum^{\infty}_{n=0} \binom{2n}{n} p^nq^n - 1 = \frac{1}{\sqrt{1 - 4pq}} - 1 = \frac{1}{|2p - 1|} - 1$ とも書けます（この等式の導出も母関数のページを参照）。戻ってくる回数の期待値は p = 1 のときは 0 となり、 p が 1/2 に近づくにつれて無限回に増えるわけです。この値が r / (1 − r) に等しいので、たとえば p > 1/2 と仮定して r / (1 − r) = −1 + 1 / (2 p − 1) とおけば r = 2 q = 1 − |p − q| となります。

[0] 期待値の定義に従って計算します。
$\begin{align} E[X] &= \sum_{k=0}^n k \binom{n}{k} p^k(1-p)^{n-k} = \sum_{k=1}^n k \binom{n}{k} p^k(1-p)^{n-k}\\ &= \sum_{k=1}^n k \frac{n}{k} \binom{n-1}{k-1} p^k(1-p)^{n-k} = \sum_{k=1}^n k \cdot \frac{n}{k} \cdot p \binom{n-1}{k-1} p^{k-1}(1-p)^{n-k}\\ &= np \sum^{n}_{k=1} \binom{n-1}{k-1} p^{k-1}(1-p)^{n-k} = np \end{align}$

[1] 分散の定義に従って計算します。まず
$\begin{align} E[X^2] &= k^2 \sum_{k=0}^n k \binom{n}{k} p^k(1-p)^{n-k} = \sum_{k=0}^n {k(k-1)+k} \binom{n}{k} p^k(1-p)^{n-k}\\ &= \sum_{k=0}^n k(k-1) \binom{n}{k} p^k(1-p)^{n-k} + \sum_{k=0}^n k \binom{n}{k} p^k(1-p)^{n-k}\\ &= \sum_{k=0}^n k(k-1) \binom{n}{k} p^k(1-p)^{n-k} + np \\ &= n(n-1) \sum_{k=2}^n k(k-1) \binom{n-2}{k-2} p^{k-2}(1-p)^{n-k} + np \\ &= n(n-1) p^2 + np \end{align}$
したがって
$\begin{align} V[X] &= E[X^2] - (E[X])^2 = n(n-1) p^2 + np - n^2p^2\\ &= np (1-p) \end{align}$

[2] この関係式から $\begin{align} g(2) &= f(2)\\ g(4) &= f(4) - f(2) g(2)\\ g(6) &= f(6) - f(4) g(2) - f(2) g(4) \\ \cdots & \cdots \\ g(2n) &= f(2n) - f(2n-2) g(2) - f(2n-4) g(4) - \cdots f(2) g(2n-2) \end{align}$ が求まり、f ( 2 n ) を用いて g ( 2 n ) を書き下すことができます。

[3] 再帰確率を 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 ステップ後に原点にいる確率をすべて足し合わせたものに等しいので $\textstyle \sum^{\infty}_{n=1} \binom{2n}{n} p^nq^n = \sum^{\infty}_{n=0} \binom{2n}{n} p^nq^n - 1 = \frac{1}{\sqrt{1 - 4pq}} - 1 = \frac{1}{|2p - 1|} - 1$ とも書けます（この等式の導出も母関数のページを参照）。戻ってくる回数の期待値は p = 1 のときは 0 となり、 p が 1/2 に近づくにつれて無限回に増えるわけです。この値が r / (1 − r) に等しいので、たとえば p > 1/2 と仮定して r / (1 − r) = −1 + 1 / (2 p − 1) とおけば r = 2 q = 1 − |p − q| となります。

[1]

[2]

[3]

[4]

Aritalab:Lecture/NetworkBiology/Random Walk

Revision as of 09:58, 1 July 2011

Contents

1次元のランダムウォーク

拡散係数

再帰確率

ギャンブラーの破産問題

有限グラフ上のランダムウォーク

参考：式の導出

Personal tools

Namespaces

Variants

Views

Actions

Search

Navigation

metabolites

Toolbox

@@ Line 64: / Line 64: @@
 ===再帰確率===
-原点から出発したランダムウォークが原点に戻ってくる確率を再帰確率といい、''p'' = ''q'' = 1/2 の時に限って 1 になります。確率 1 で原点に戻るとき、ウォークは再帰的であるといいます。''p'' &ne; 1/2 のときウォークは再帰的でなく、再帰確率は 1 &minus; |''p'' &minus; ''q''| になります<ref>
+原点から出発したランダムウォークが原点に戻ってくる確率を再帰確率といいます。
+原点から出発して 2''n'' ステップ後に再び原点に戻っている確率 ''f'' ( 2 ''n'' ) は、左右にちょうど ''n'' 回ずつ移動すればよいので
+<math> f(2n) = \frac{2n!}{n! n!} p^n q^n \ </math>
+になります。''f'' (0) = 1 です。これは原点に何回戻ってもよい確率なので、 2''n'' ステップ後に初めて原点に戻ってくる確率を ''g'' ( 2 ''n'' ) と書きます。このとき、
+<math>
+\begin{align}
+f(2n) &= g(2) f(2n - 2) \\
+&+ g(4) f(2n - 4) \\
+&+ g(6) f(2n - 6) \\
+&+ \cdots \\
+&+ g(2n - 2) f(2) + g(2n) \\
+&= \sum^n_{m=1} g(2m) f(2n - 2m)
+\end{align}
+</math>
+となります<ref>この関係式から
+<math>
+\begin{align}
+g(2) &= f(2)\\
+g(4) &= f(4) - f(2) g(2)\\
+g(6) &= f(6) - f(4) g(2) - f(2) g(4) \\
+\cdots & \cdots \\
+g(2n) &= f(2n) - f(2n-2) g(2) - f(2n-4) g(4) - \cdots f(2) g(2n-2)
+\end{align}
+</math>
+が求まり、''f'' ( 2 ''n'' ) を用いて ''g'' ( 2 ''n'' ) を書き下すことができます。</ref>。ここで ''f'', ''g'' の母関数を考えます。 ''g'' は 2 ''n'' 回目で初めて原点に戻ることを意味する関数なので ''n'' = 1 からスタートするところに注意しましょう。
+<math>
+\begin{align}
+F(z) &= \sum^{\infty}_{n=0} f(2n) z^{2n} \\
+G(z) &= \sum^{\infty}_{n=1} g(2n) z^{2n}
+\end{align}
+</math>
+ここで ''f'' と ''g'' の関係式から
+<math>
+\begin{align}
+f(2n) &= \sum^n_{m=1} g(2m) f(2n - 2m)\\
+f(2n) z^{2n} & = \sum^n_{m=1} g(2m) z^{2m} f(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]\\
+\end{align}
+</math>
+さらに
+<math>
+\begin{align}
+f(2) &= g(2)\\
+f(4) &= g(4) + g(2) f(2)\\
+f(6) &= g(6) + g(4) f(2) + g(2) f(4)\\
+ \vdots \ &= \ \vdots
+\end{align}
+</math>
+という関係を縦方向に眺めることによって、右辺の2重和の順序を入れ替えます。
+<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]\\
+&= \sum^{\infty}_{m=1} g(2m)z^{2m} \sum^{\infty}_{n=m} f(2n - 2m) z^{2n-2m}\\
+&= G(z) F(z)
+\end{align}
+</math>
+左辺は <math>f(2) = 1 </math> を含まないので　<math>F(s) - 1\ </math> となり、<math> G(z) = \frac{F(s) - 1}{F(s)}\ </math> となります。
+無限級数 <math> F(s)\ </math> が発散するときは <math> G(z) \rightarrow 1 </math> となって再帰確実であり（必ず原点にもどる）、有限な値に収束するときは <math> G(z) < 1\ </math> で再帰不確実です。
+<ref>
 再帰確率を ''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'' ) になります。戻ってくる回数の期待値は
@@ Line 81: / Line 156: @@
 ;考察
 : 公正なコインによる賭けでは、どんなに負けていても賭けを継続していれば収支は必ず 0 に戻せる（再帰性）。
 ===ギャンブラーの破産問題===