ランダムウォークと電気回路

更新 2021/03/07

グラフ上の単純ランダムウォークについて
電気回路との対応についての定理
定理の応用例

です！

単純ランダムウォーク

グラフ（ネットワークのようなもの）のある頂点から出発して，各ステップでつながっている頂点に等確率で移動するようなモデルを単純ランダムウォークと言います。
例えば，図において青い点にいるとき，次のステップでは赤い点のどれかにそれぞれ
13\dfrac{1}{3}31​
 で移動します。グラフが三角形や線分などシンプルな形なら入試の題材にもなります。
今回は連結なグラフとその中の二つの頂点
A,BA,BA,B
 が与えられたときに，頂点 vvv から出発する単純ランダムウォークが BBB よりも AAA に先に到着する確率 pvp_vpv​ について考えます。

漸化式を立てる

$p_A=1$ ， $p_B=0$
$A,B$ 以外の各頂点 $v$ について， $p_v=\dfrac{1}{d_v}\displaystyle\sum_{u\in N(v)}p_u$

ただし， $N(v)$ は $v$ に隣接する頂点の集合で， $d_v$ は $v$ の次数（ $v$ に隣接している頂点の個数）を表します。

一つ目の式は明らかです。二つ目については， $v$ から $B$ よりも $A$ に先に到着する確率を最初の1ステップで場合分けして考えると分かります。

この漸化式（連立方程式）を解けば $p_v$ が分かります。

電気回路の対応

突然ですが，もとのグラフの各辺を $1\Omega$ の抵抗とした電気回路を考えます。電圧源を用いて $A$ の電位を $1$ V， $B$ の電位を $0$ Vとします。このとき各頂点 $v$ の電位は $\phi_v$ になるとします。

定理

任意の頂点 $v$ について $p_v=\phi_v$

つまり，実際に回路を作って電流を流してみて電位を見れば単純ランダムウォークで先に $A$ にたどりつく確率が分かるのです！

証明

・ $\phi_A=1,\phi_B=0$ より $p_A=\phi_A,p_B=\phi_B$

・次に電気回路において， $A,B$ 以外の頂点 $v$ について成り立つ方程式を考える。

頂点 $u$ から頂点 $v$ に流れる電流はオームの法則より $\phi_u-\phi_v$

よって，頂点 $v$ についてキルヒホッフ第一法則より $\displaystyle\sum_{u\in N(v)}(\phi_u-\phi_v)=0$

これを変形すると $\phi_v=\dfrac{1}{d_v}\displaystyle\sum_{u\in N(v)}\phi_u$

これは $p_v$ の漸化式（連立方程式）の形と全く同じである。 $p_v$ を求めるための方程式と $\phi_v$ を求めるための方程式が同じなので定理は示された（→注）。

注：厳密には方程式の数が十分であること（解がただ1つ存在すること）を証明する必要があります。ラプラシアン行列の性質を使えばわりと簡単にできますが省略します。

応用例

電気回路との対応の定理が威力を発揮する例です。

$p=\dfrac{1}{2}$ の場合の破産の確率が $1-\dfrac{n}{N}$ であることが漸化式を立てることなく一瞬で分かります！（ $1\Omega$ の抵抗が $N$ 個直列につながった回路を考える） →破産の確率と漸化式

今日の記事は知人のA氏によるものです，感謝〜〜

この記事の監修者

マスオ

高校数学の美しい物語の管理人。「わかりやすいこと」と「ごまかさないこと」の両立を意識している。著書に『高校数学の美しい物語』『超ディープな算数の教科書』。記事の誤植やわかりにくい等のご指摘はお気軽にメールください！