Aritalab:Lecture/NetworkBiology/Random Walk

ランダムウォーク

一次元

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

_nC_k p^k ( 1- p )^n-k

であらわされ、二項分布 (英語でbinomial distributionといいます) B(n, p ) に従います。位置の期待値は np ^[1], 分散は np (1 - p) ^[2]です。

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

グラフ G(V,E) の各頂点 u から出る辺を等確率 $1/d(u)$ で選んで動くグラフ上のランダムウォークを考えよう。非周期性を仮定したいので、以下では二部グラフでない連結なものだけを考慮する。

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

証明

まずランダムウォークの定常分布 $\bar \pi$ が $\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 \frac{1}{\pi_u}$ であることを使うと証明は終わり。

補題

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

$\textstyle 2|E| = h_{u,u} \cdot d(u) = \sum_{v \in adj(u)} (1+ h_{v,u}) > 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}$

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

[1]

[2]

Aritalab:Lecture/NetworkBiology/Random Walk

Contents

ランダムウォーク

一次元

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

Personal tools

Namespaces

Variants

Views

Actions

Search

Navigation

metabolites

Toolbox