Aritalab:Lecture/NetworkBiology/Random Walk

Latest revision as of 15:01, 27 August 2015

[edit] 1次元ランダムウォーク

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

$\textstyle\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 乗の期待値は

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

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

まとめ

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

[edit] 再帰確率

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

再帰確率 $\, r = 1 - | p - q |$
再帰確率が r < 1 のときに原点に戻ってくる回数の期待値 $\textstyle \frac{r}{1-r} = \frac{1}{|2p - 1|} - 1$

となります。^[3]

k＝1 の場合

[edit] 反射壁と吸収壁

反射壁や吸収壁を k^* と書くと

反射壁があるとき、n ステップ後に位置 k に至る経路数は $P(k, n; k^*) = P(k, n) + P(2k^* - k, n) \,$
吸収壁があるとき、n ステップ後に位置 k に至る経路数は $P(k, n; k^*) = P(k, n) - P(2k^* - k, n) \,$

となります。(詳細)

[edit] 2次元ランダムウォーク

2 次元の場合は上下左右の 4 方向に移動できます。2n ステップ後に原点に戻っている場合、左右と上下にそれぞれ k, n − k ステップずつ進むと仮定できます。

$\begin{align} p^{(2n)}_{00} &= \textstyle\sum^n_{k=0} \frac{(2n)!}{k! k! (n-k)! (n-k)!} \big( \frac{1}{4} \big)^{2n} \\ &=\textstyle\frac{(2n)!}{(n!)^2} \sum^n_{k=0} \big( \frac{n!}{k!(n-k)!} \big)^2 \big( \frac{1}{4} \big)^{2n} \\ &=\textstyle\frac{(2n)!}{(n!)^2} \sum^n_{k=0} \binom{n}{k}^2 \big( \frac{1}{4} \big)^{2n} \end{align}$

ここでヴァンデルモンドの畳み込みから $\textstyle\sum^n_{k=0}\binom{n}{k}^2 = \binom{2n}{n}$ なので

$p^{(2n)}_{00} = \textstyle \frac{(2n)!}{(n!)^2}\binom{2n}{n}\big(\frac{1}{4}\big)^{2n} = \big[ \frac{(2n)!}{(n!)^2} \big]^2 \frac{1}{4^{2n}}$

さらにスターリングの公式 $n! \sim n^n e^{-n} \sqrt{2\pi n}$ を使うと

$p^{(2n)}_{00} \sim \textstyle \big[ \frac{(2n)^{2n} e^{-2n} \sqrt{4 \pi n} }{n^{2n} e^{-2n} 2 \pi n} \big]^2 \frac{1}{4^{2n}} = \big[ \frac{4^n}{\sqrt{\pi n}} \big]^2 \frac{1}{4^{2n}} = \frac{1}{\pi n}$

原点に戻る回数の総計は発散しますが（再帰確実）、 $p^{(2n)}_{00} \xrightarrow{n \rightarrow \infty} 0$ のため、原点はゼロ再帰性を満たします。全ての点は同値類に属すので、平面全体がゼロ再帰性（定常分布 π_ij = 0) となります。

[edit] 3次元ランダムウォーク

3 次元の場合、上下、左右、前後にそれぞれ k, j, (n − k − j) 回ずつ移動して 2n ステップ後に原点に戻ると仮定できます。

$\begin{align} p^{(2n)}_{000} &= \textstyle\sum_{(j+k)\leq n} \frac{(2n)!}{(k!)^2 (j!)^2 [(n-k-j)!]^2} \big( \frac{1}{6} \big)^{2n} \\ &=\textstyle\frac{(2n)!}{(n!)^2 2^{2n}} \sum_{(j+k)\leq n} \big( \frac{n!}{k!j!(n-k-j)!} \big)^2 \big( \frac{1}{3} \big)^{2n} \\ \end{align}$

この式を閉じた形にするのは大変なので上限値を見積もりましょう。

一般に 3 項分布から以下が成立します。

$\textstyle\sum_{(j+k)\leq n}\frac{n!}{k!j!(n-k-j)!} \frac{1}{3^n} = 1, \quad \textstyle\frac{n!}{k!j!(n-k-j)!} \leq \frac{n!}{[(n/3)!]^3}$

これより大雑把な見積もりですが

$\begin{align} p^{(2n)}_{000} &\leq \textstyle\frac{(2n)!}{2^{2n}(n!)^2} \frac{n!}{[(n/3)!]^3} \frac{1}{3^n}\\ &\sim \textstyle\frac{1}{2^{2n}} \frac{(2n)^{2n} e^{-2n}\sqrt{4\pi n}}{n^n e^{-n} \sqrt{2 \pi n} (n/3)^n e^{-n} (\sqrt{2\pi n/3})^3} \frac{1}{3^n}\\ &= \textstyle\frac{1}{2}\big(\frac{3}{\pi n}\big)^{3/2} \end{align}$

原点に戻る回数の総計が有限となるため $\textstyle\sum^{\infty}_{n=0} p^{(2n)}_{000} = \textstyle\sum^{\infty}_{n=0} \frac{c}{n^{3/2}} < \infty \ (c = const.)$ 、空間全体は再帰不確実 (transient) です。

ここまでのランダムウォークをみると、m 次元ランダムウォークは

$p^{(2n)}_{0^m} \leq c/(\sqrt{\pi n})^{m/2}$

であることが予想されます。3 次元以降はすべて非再帰的になります。

[edit] 拡散係数

ランダムウォークを時間の関数として捉えるため、τ 秒毎にステップを刻むことにして歩幅を δ 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 時間

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

グラフ 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$ 。

また $\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) と呼びます。

[edit] 参考：式の導出

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

↑ 期待値の定義に従って計算します。
$\begin{align} E[X] &= \textstyle\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}\\ &= \textstyle\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}\\ &= \textstyle 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] &=\textstyle 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}\\ &=\textstyle \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}\\ &=\textstyle \sum_{k=0}^n k(k-1) \binom{n}{k} p^k(1-p)^{n-k} + np \\ &=\textstyle 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}$
↑
再帰確率を c とおきます。一度戻ったらそこからランダムウォークをまた始めるとすれば
- ランダムウォークが2回以上ゼロ地点に戻る確率 c²
- ランダムウォークが3回以上ゼロ地点に戻る確率 c³
. となります。だから
- 戻ってこない確率 = 1 − c
- ちょうど１回戻る確率 = c − c² = c(1 − c)
- ちょうど２回戻る確率 = c² − c³ = c² (1 − c)
.
- ちょうど n 回戻る確率 = cⁿ − cⁿ⁺¹ = cⁿ (1 − c)
です。戻ってくる回数の期待値は Σ n · cⁿ (1 − c) = c / (1 - c) です。

[0] 期待値の定義に従って計算します。
$\begin{align} E[X] &= \textstyle\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}\\ &= \textstyle\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}\\ &= \textstyle 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] &=\textstyle 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}\\ &=\textstyle \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}\\ &=\textstyle \sum_{k=0}^n k(k-1) \binom{n}{k} p^k(1-p)^{n-k} + np \\ &=\textstyle 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] 再帰確率を c とおきます。一度戻ったらそこからランダムウォークをまた始めるとすれば
ランダムウォークが2回以上ゼロ地点に戻る確率 c²
ランダムウォークが3回以上ゼロ地点に戻る確率 c³
. となります。だから
戻ってこない確率 = 1 − c
ちょうど１回戻る確率 = c − c² = c(1 − c)
ちょうど２回戻る確率 = c² − c³ = c² (1 − c)
.
ちょうど n 回戻る確率 = cⁿ − cⁿ⁺¹ = cⁿ (1 − c)
です。戻ってくる回数の期待値は Σ n · cⁿ (1 − c) = c / (1 - c) です。

[4] ランダムウォークが2回以上ゼロ地点に戻る確率 c²

[5] ランダムウォークが3回以上ゼロ地点に戻る確率 c³

[6] 戻ってこない確率 = 1 − c

[7] ちょうど１回戻る確率 = c − c² = c(1 − c)

[8] ちょうど２回戻る確率 = c² − c³ = c² (1 − c)

[9] ちょうど n 回戻る確率 = cⁿ − cⁿ⁺¹ = cⁿ (1 − c)

[1]

[2]

[3]

@@ Line 1: / Line 1: @@
 {{Lecture/Header}}
-==1次元のランダムウォーク==
+==1次元ランダムウォーク==
 原点から出発して1ステップ毎に確率 ''p'' で + 1, ''q'' (= 1 &minus; ''p'') で &minus; 1 動くランダムウォークを考えましょう。
 ''n'' ステップ後に、正の方向に ''k'' 回進んでいる確率は
-<center> <sub>n</sub><big>C</big><sub>k</sub> ''p<sup>k</sup>'' ''q<sup>n - k</sup>'' </center>
-であらわされ、二項分布 (binomial distribution) B( ''n'', ''p'' ) に従います。二項分布で正の方向に進むステップ数 ''k'' の期待値は ''np'' <ref>期待値の定義に従って計算します。
+<math>\textstyle\binom{n}{k} p^k q^{(n-k)}\ </math>
+であらわされ、二項分布 (binomial distribution) B( ''n'', ''p'' ) に従います。二項分布で正の方向に進むステップ数 ''k'' の期待値は ''np'' <ref>期待値の定義に従って計算します。<br/>
 <math>
 \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}\\
+E[X] &= \textstyle\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}\\
+&= \textstyle\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
+&= \textstyle np \sum^{n}_{k=1} \binom{n-1}{k-1} p^{k-1}(1-p)^{n-k} = np
 \end{align}
 </math>
-</ref>なので、移動位置の期待値は
+</ref>なので、''n'' ステップ後の位置の期待値は
-<center>
-E[ ''k'' &minus; (''n'' &minus; ''k'')] =  E[ 2 ''k'' &minus; ''n'' ] = 2 ''np'' &minus; ''n'' = ''n'' (''p'' &minus; ''q'' )
+<math>E[k - (n -k)] = E[2k - n] = 2 np - n = n(p - q) \ </math>
-</center>
 になります。
-二項分布の分散は ''npq'' <ref>分散の定義に従って計算します。まず
+二項分布の分散は ''npq'' です<ref>分散の定義に従って計算します。まず<br/>
 <math>
 \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}\\
+E[X^2] &=\textstyle 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}\\
+&=\textstyle \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 \\
+&=\textstyle \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 \\
+&=\textstyle 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}</math>
@@ Line 35: / Line 37: @@
 \end{align}
 </math>
-</ref>なので、原点からの移動距離の２乗の期待値（分散）は
+</ref>。原点からの移動距離の 2 乗の期待値は
-<center>
-E[ (2 ''k'' &minus; ''n'' )<sup>2</sup> ] = E[ 4 ''k''<sup>2</sup> &minus; 4 ''kn'' + ''n''<sup>2</sup>] = 4( ( ''np'' )<sup>2</sup> + ''npq'' ) &minus; 4 ''np'' ''n'' + ''n''<sup>2</sup>
-</center>
-です。 ''p'' = ''q'' = 1/2 の場合、左右に同じ確率で広がるので位置の期待値は 0 です。分散は ''n''、つまり原点からの移動距離の期待値は ''n''<sup>1/2</sup> になります。
-===拡散係数===
+<math>
+\begin{align}
+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
+\end{align}
+</math>
-ランダムウォークを時間の関数として捉えるため、''&tau;'' 秒毎にステップを刻むことにして歩幅を ''&delta;'' cm とします。つまり、ステップ数 ''n'' = ''t'' / ''&tau;'' です。拡散の度合いは分散であらわされます。対称な二項分布の分散は ''n'' = (''t''/''&tau;'') ''&delta;''<sup>2</sup> = 2 (''&delta;''<sup>2</sup> /2 ''&tau;'') ''t'' となります（分散は距離の 2 乗平均なので ''&delta;'' が 2 乗されるところに注意）。
+です。 ''p'' = ''q'' = 1/2 の場合は左右に同じ確率で広がり、位置の期待値は 0 です。そのとき移動距離の期待値は ''n''<sup>1/2</sup> です。
-拡散係数を ''D'' = ''&delta;''<sup>2</sup> /2 ''&tau;'' (単位は cm<sup>2</sup>/sec) と書くと、分散は 2 ''Dt'' です。拡散に要する時間は、''t'' = (距離)<sup>2</sup> / 2 ''D'' になります。
-水中の小分子なら ''D'' &sim; 10<sup>&minus; 5</sup> 、空気中の小分子なら ''D'' &sim; 10<sup>&minus; 1</sup> 程度であることが知られています。
-;考察
+;まとめ
-コーヒークリームがカップの中で広がったり、隣の人が香水をつけているかすぐ分かるのは、分子の拡散が原因ではなく水や空気の対流
+* 位置の期待値 <math> (p-q)n \ </math>
-や攪拌のおかげです。拡散に必要な時間を計算してみましょう。
+* 移動距離の期待値 <math>\textstyle \sqrt{(p-q)^2n^2 + 4pqn} </math>
-* 水中の小分子が拡散のみで ''x'' = 10<sup>-4</sup> cm = 1 &mu; m (大腸菌のサイズ) 進むのに必要な時間
-:: ''t'' = ''x''<sup>2</sup>/2''D'' = 10<sup>-8</sup>/(2 &times; 10<sup>-5</sup>) = 5 &times; 10<sup>-4</sup>　秒 (0.5 ミリ秒)
-* 水中の小分子が拡散のみで ''x'' = 10 cm 進むのに必要な時間
-:: ''t'' = ''x''<sup>2</sup>/2''D'' = (10)<sup>2</sup> /(2 &times; 10<sup>-5</sup>) = 5 &times; 10<sup>6</sup> 秒 = 2 ヶ月
-* 空気中の小分子が拡散のみで ''x'' = 1 m 進むのに必要な時間
-:: ''t'' = ''x''<sup>2</sup>/2''D'' = (100)<sup>2</sup> / (2 &times; 10<sup>-1</sup>) = 5 &times; 10<sup>4</sup> 秒 = 14 時間
-===再帰性===
+===再帰確率===
-原点から出発したランダムウォークが原点に戻ってくる確率を再帰確率といい、''p'' = ''q'' = 1/2 の時に限って 1 になります。確率 1 で原点に戻るとき、ウォークは再帰的であるといいます。''p'' &ne; 1/2 のときウォークは再帰的でなく、再帰確率は 1 &minus; |''p'' &minus; ''q''| になります<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'' ) になります。戻ってくる回数の期待値は
-<math>\textstyle \sum^{\infty}_{n=0} n \cdot r^n (1-r) = \frac{r}{1-r}</math>
+原点から出発したランダムウォークが原点に戻ってくる確率を再帰確率といいます。一次元ランダムウォークの場合
+* 再帰確率 <math>\, r =  1 - | p - q | </math>
+* 再帰確率が ''r'' < 1 のときに原点に戻ってくる回数の期待値 <math>\textstyle \frac{r}{1-r} = \frac{1}{|2p - 1|} - 1</math>
+となります。<ref>
+再帰確率を c とおきます。一度戻ったらそこからランダムウォークをまた始めるとすれば
-になります（この等式の導出は[[Aritalab:Lecture/Basic/Generating_Function|母関数]]のページを参照）。一方で、ランダムウォークが原点に戻ってくる回数は ''n'' ステップ後に原点にいる確率をすべて足し合わせたものに等しいので
+* ランダムウォークが2回以上ゼロ地点に戻る確率 c<sup>2</sup>
+* ランダムウォークが3回以上ゼロ地点に戻る確率 c<sup>3</sup>
+.
-<math>\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</math>
+となります。だから
-とも書けます（この等式の導出も[[Aritalab:Lecture/Basic/Generating_Function|母関数]]のページを参照）。戻ってくる回数の期待値は ''p'' = 1 のときは 0 となり、 ''p'' が 1/2 に近づくにつれて無限回に増えるわけです。この値が ''r'' / (1 &minus; ''r'') に等しいので、たとえば ''p'' > 1/2 と仮定して ''r'' / (1 &minus; ''r'')  = &minus;1 + 1 / (2 ''p'' &minus; 1) とおけば ''r'' = 2 ''q'' = 1 &minus; |''p'' &minus; ''q''| となります。
+* 戻ってこない確率 = 1 − c
-</ref>。
+* ちょうど１回戻る確率 = c − c<sup>2</sup> = c(1 − c)
+* ちょうど２回戻る確率 = c<sup>2</sup> − c<sup>3</sup> = c<sup>2</sup> (1 − c)
+.
+* ちょうど n 回戻る確率 = c<sup>n</sup> − c<sup>n+1</sup> = c<sup>n</sup> (1 − c)
-再帰的な場合、つまり ''p'' = ''q'' = 1/2 であれば、戻るまでの期待時間を考えることは意味があります。
+です。戻ってくる回数の期待値は Σ n · c<sup>n</sup>  (1 − c) = c / (1 - c) です。
-これを平均再帰時間といい ''n'' ステップ後にはじめて原点に戻ってくる確率に ''n'' をかけて和をとると求まります。一次元のランダムウォークでも平均再帰時間は無限大になります。
+</ref>
+{{GenerateIndex|Aritalab|Lecture/NetworkBiology/Random_Walk/Recurrence|3}}
-;考察
+===[[Aritalab:Lecture/NetworkBiology/Random_Walk/Reflection|反射壁と吸収壁]]===
-: 公正なコインによる賭けでは、どんなに負けていても賭けを継続していれば収支は必ず 0 に戻せる（再帰性）。
+反射壁や吸収壁を ''k<sup>*</sup>'' と書くと
+* 反射壁があるとき、''n'' ステップ後に位置 ''k'' に至る経路数は <math> P(k, n; k^*) = P(k, n) + P(2k^* - k, n) \,</math>
+* 吸収壁があるとき、''n'' ステップ後に位置 ''k'' に至る経路数は <math> P(k, n; k^*) = P(k, n) - P(2k^* - k, n) \,</math>
+となります。([[Aritalab:Lecture/NetworkBiology/Random_Walk/Reflection|詳細]])
+==2次元ランダムウォーク==
+次元の場合は上下左右の 4 方向に移動できます。2n ステップ後に原点に戻っている場合、左右と上下にそれぞれ k, n &minus; k ステップずつ進むと仮定できます。
+<math>
+\begin{align}
+p^{(2n)}_{00} &= \textstyle\sum^n_{k=0} \frac{(2n)!}{k! k! (n-k)! (n-k)!} \big( \frac{1}{4} \big)^{2n} \\
+&=\textstyle\frac{(2n)!}{(n!)^2} \sum^n_{k=0} \big( \frac{n!}{k!(n-k)!} \big)^2 \big( \frac{1}{4} \big)^{2n} \\
+&=\textstyle\frac{(2n)!}{(n!)^2} \sum^n_{k=0} \binom{n}{k}^2 \big( \frac{1}{4} \big)^{2n}
+\end{align}
+</math>
-===ギャンブラーの破産問題===
+ここでヴァンデルモンドの畳み込みから <math>\textstyle\sum^n_{k=0}\binom{n}{k}^2 = \binom{2n}{n}</math> なので
-二人のプレーヤーがコインを ''k''<sub>1</sub> と ''k''<sub>2</sub> 枚ずつ持っています。確率 1/2 で勝てばコインを 1 枚うけとり、負ければ 1 枚渡します。勝負は原点から出発して左右に 1/2 の確率で移動するランダムウォークに相当し、時刻 ''t'' における位置はプレーヤー 1 が得たコインの枚数（勝ち数）です。状態 &minus; ''k''<sub>1</sub> になったらプレーヤー 1 が破産してゲームは終了し、''k''<sub>2</sub> になったらプレーヤー 2 が破産してゲームは終了します。このゲームは、状態 ''k''<sub>1</sub> と ''k''<sub>2</sub> が吸収状態になっているマルコフ連鎖とみなせます。プレーヤー 1 が破産する前に ''k''<sub>2</sub> 枚のコインを獲得する確率 ''q'' を求めましょう。
-時刻 ''t'' において位置が ''i'' にいる確率を<math>P^t_{i}</math> と書きましょう。すると
+<math>
+p^{(2n)}_{00} = \textstyle \frac{(2n)!}{(n!)^2}\binom{2n}{n}\big(\frac{1}{4}\big)^{2n} = \big[ \frac{(2n)!}{(n!)^2} \big]^2 \frac{1}{4^{2n}}
+</math>
-<math>\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) </math>
+さらにスターリングの公式 <math>n! \sim n^n e^{-n} \sqrt{2\pi n}</math> を使うと
-となります。また、ゲームは公正なため、何回目の勝負であってもプレーヤー 1 が持つコイン数の期待値は 0 です。つまり時刻 ''t'' について数学的帰納法を用いると、常に
+<math>
+p^{(2n)}_{00} \sim \textstyle \big[ \frac{(2n)^{2n} e^{-2n} \sqrt{4 \pi n} }{n^{2n} e^{-2n} 2 \pi n} \big]^2 \frac{1}{4^{2n}} = \big[ \frac{4^n}{\sqrt{\pi n}} \big]^2 \frac{1}{4^{2n}} = \frac{1}{\pi n}
+</math>
-<math>\textstyle \sum^{k_2}_{i = -k_1} i P^t_{i} = 0 \ (t = 0, 1, \cdots)</math>
+原点に戻る回数の総計は発散しますが（再帰確実）、 <math>p^{(2n)}_{00} \xrightarrow{n \rightarrow \infty} 0</math> のため、原点はゼロ再帰性を満たします。全ての点は同値類に属すので、平面全体がゼロ再帰性（定常分布 &pi;<sub>ij</sub> = 0) となります。
-です。極限を取ると
+==3次元ランダムウォーク==
-<math>\textstyle \lim_{t\rightarrow \infty} \sum^{k_2}_{i = -k_1} i P^t_{i} = k_2 q - k_1 (1-q) = 0 </math>
+次元の場合、上下、左右、前後にそれぞれ k, j, (n &minus; k &minus; j) 回ずつ移動して 2n ステップ後に原点に戻ると仮定できます。
-となるので <math> q = k_1 / (k_1 + k_2) </math> です。つまりゲームに勝つ確率は、開始時の持ち点に比例します。
+<math>
+\begin{align}
+p^{(2n)}_{000} &= \textstyle\sum_{(j+k)\leq n} \frac{(2n)!}{(k!)^2 (j!)^2 [(n-k-j)!]^2} \big( \frac{1}{6} \big)^{2n} \\
+&=\textstyle\frac{(2n)!}{(n!)^2 2^{2n}} \sum_{(j+k)\leq n} \big( \frac{n!}{k!j!(n-k-j)!} \big)^2 \big( \frac{1}{3} \big)^{2n} \\
+\end{align}
+</math>
+この式を閉じた形にするのは大変なので上限値を見積もりましょう。
+一般に 3 項分布から以下が成立します。
+<math>
+\textstyle\sum_{(j+k)\leq n}\frac{n!}{k!j!(n-k-j)!} \frac{1}{3^n} = 1, \quad
+\textstyle\frac{n!}{k!j!(n-k-j)!} \leq \frac{n!}{[(n/3)!]^3}
+</math>
+これより大雑把な見積もりですが
+<math>
+\begin{align}
+p^{(2n)}_{000} &\leq \textstyle\frac{(2n)!}{2^{2n}(n!)^2} \frac{n!}{[(n/3)!]^3} \frac{1}{3^n}\\
+&\sim \textstyle\frac{1}{2^{2n}} \frac{(2n)^{2n} e^{-2n}\sqrt{4\pi n}}{n^n e^{-n} \sqrt{2 \pi n} (n/3)^n e^{-n} (\sqrt{2\pi n/3})^3} \frac{1}{3^n}\\
+&= \textstyle\frac{1}{2}\big(\frac{3}{\pi n}\big)^{3/2}
+\end{align}
+</math>
+原点に戻る回数の総計が有限となるため <math>\textstyle\sum^{\infty}_{n=0} p^{(2n)}_{000} = \textstyle\sum^{\infty}_{n=0} \frac{c}{n^{3/2}} < \infty \ (c = const.)</math>、空間全体は再帰不確実 (transient) です。
+ここまでのランダムウォークをみると、m 次元ランダムウォークは
+<math>
+p^{(2n)}_{0^m} \leq c/(\sqrt{\pi n})^{m/2}
+</math>
+であることが予想されます。3 次元以降はすべて非再帰的になります。
+==拡散係数==
+ランダムウォークを時間の関数として捉えるため、''&tau;'' 秒毎にステップを刻むことにして歩幅を ''&delta;'' cm とします。つまり、ステップ数 ''n'' = ''t'' / ''&tau;'' です。拡散の度合いは分散であらわされます。対称な二項分布の分散は ''n'' = (''t''/''&tau;'') ''&delta;''<sup>2</sup> = 2 (''&delta;''<sup>2</sup> /2 ''&tau;'') ''t'' となります（分散は距離の 2 乗平均なので ''&delta;'' が 2 乗されるところに注意）。
+拡散係数を ''D'' = ''&delta;''<sup>2</sup> /2 ''&tau;'' (単位は cm<sup>2</sup>/sec) と書くと、分散は 2 ''Dt'' です。拡散に要する時間は、''t'' = (距離)<sup>2</sup> / 2 ''D'' になります。
+水中の小分子なら ''D'' &sim; 10<sup>&minus; 5</sup> 、空気中の小分子なら ''D'' &sim; 10<sup>&minus; 1</sup> 程度であることが知られています。
 ;考察
-: 公正なコインを用いた賭けでも、資金が少ないギャンブラーが資金の多い胴元に勝つ見込みは少ない。
+コーヒークリームがカップの中で広がったり、隣の人が香水をつけているかすぐ分かるのは、分子の拡散が原因ではなく水や空気の対流
+や攪拌のおかげです。拡散に必要な時間を計算してみましょう。
+* 水中の小分子が拡散のみで ''x'' = 10<sup>-4</sup> cm = 1 &mu; m (大腸菌のサイズ) 進むのに必要な時間
+:: ''t'' = ''x''<sup>2</sup>/2''D'' = 10<sup>-8</sup>/(2 &times; 10<sup>-5</sup>) = 5 &times; 10<sup>-4</sup>　秒 (0.5 ミリ秒)
+* 水中の小分子が拡散のみで ''x'' = 10 cm 進むのに必要な時間
+:: ''t'' = ''x''<sup>2</sup>/2''D'' = (10)<sup>2</sup> /(2 &times; 10<sup>-5</sup>) = 5 &times; 10<sup>6</sup> 秒 = 2 ヶ月
+* 空気中の小分子が拡散のみで ''x'' = 1 m 進むのに必要な時間
+:: ''t'' = ''x''<sup>2</sup>/2''D'' = (100)<sup>2</sup> / (2 &times; 10<sup>-1</sup>) = 5 &times; 10<sup>4</sup> 秒 = 14 時間
 == 有限グラフ上のランダムウォーク ==
@@ Line 109: / Line 175: @@
 また
 <math>\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

Aritalab:Lecture/NetworkBiology/Random Walk

Latest revision as of 15:01, 27 August 2015

Contents

[edit] 1次元ランダムウォーク

[edit] 再帰確率

[edit] 反射壁と吸収壁

[edit] 2次元ランダムウォーク

[edit] 3次元ランダムウォーク

[edit] 拡散係数

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

[edit] 参考：式の導出

Personal tools

Namespaces

Variants

Views

Actions

Search

Navigation

metabolites

Toolbox