Aritalab:Lecture/NetworkBiology/Random Walk

Revision as of 16:41, 7 July 2010

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

グラフ 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}$ であることを使うと証明は終わり。