1. 高校数学の美しい物語
  2. ランダムウォークと電気回路

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

更新日時 2021/03/07
  • グラフ上の単純ランダムウォークについて

  • 電気回路との対応についての定理

  • 定理の応用例

です!

目次
  • 単純ランダムウォーク

  • 漸化式を立てる

  • 電気回路の対応

  • 応用例

単純ランダムウォーク

グラフ(ネットワークのようなもの)のある頂点から出発して,各ステップでつながっている頂点に等確率で移動するようなモデルを単純ランダムウォークと言います。

単純ランダムウォーク

例えば図において青い点にいるとき,次のステップでは赤い点のどれかにそれぞれ 13\dfrac{1}{3} で移動します。グラフが三角形とか線分とかシンプルな形なら入試の題材にもなります。

今回は連結なグラフとその中の二つの頂点 A,BA,B が与えられたときに, 頂点 vv から出発する単純ランダムウォークが BB よりも AA に先に到着する確率 pvp_v について考えます。

漸化式を立てる

  • pA=1p_A=1pB=0p_B=0

  • A,BA,B 以外の各頂点 vv について, pv=1dvuN(v)pup_v=\dfrac{1}{d_v}\displaystyle\sum_{u\in N(v)}p_u

ただし,N(v)N(v)vv に隣接する頂点の集合で,dvd_vvv の次数(vv に隣接している頂点の個数)を表します。

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

この漸化式(連立方程式)を解けば pvp_v が分かります。

電気回路の対応

突然ですが,もとのグラフの各辺を 1Ω1\Omega の抵抗とした電気回路を考えます。電圧源を用いて AA の電位を 11 V,BB の電位を 00 Vとします。このとき各頂点 vv の電位は ϕv\phi_v になるとします。

定理:任意の頂点 vv について pv=ϕvp_v=\phi_v

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

証明

ϕA=1,ϕB=0\phi_A=1,\phi_B=0 より pA=ϕA,pB=ϕBp_A=\phi_A,p_B=\phi_B

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

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

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

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

これは pvp_v の漸化式(連立方程式)の形と全く同じである。 pvp_v を求めるための方程式と ϕv\phi_v を求めるための方程式が同じなので定理は示された(→注)。

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

応用例

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

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

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

人気記事
  1. 高校数学の美しい物語
  2. ランダムウォークと電気回路