電気回路網と有効抵抗

同義語:electrical networks and effective resistance有効抵抗effective resistance電気回路網electrical networkRayleighの単調性原理Nash-Williamsの不等式

概要

電気回路網と有効抵抗(electrical networks and effective resistance)とは、グラフの各辺に正のコンダクタンスを与えた回路網と、2 頂点 $a,z$ に電位差をかけたとき回路全体が示す抵抗の値 $R_{\mathrm{eff}}(a,z)$ のことである。辺をコンダクタンスに比例する確率で選ぶランダムウォークでは、電位は先に $a$ に着く確率であり、$a$ を出て戻る前に $z$ に着く確率は $1/(c_aR_{\mathrm{eff}})$ である。有効抵抗は単位流のエネルギーの最小値(Thomson の原理)で、辺の抵抗について単調であり(Rayleigh の単調性原理)、往復時間は $2R_{\mathrm{eff}}\sum_ec_e$ に等しい。無限グラフでは無限遠への有効抵抗が無限大であることが再帰性と同値になる。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: Markov連鎖, ランダムウォーク, Laplacian行列

電気回路網(electrical network)とは、グラフの各辺に正の数(コンダクタンス、抵抗の逆数)を割り当てたものであり、2 つの頂点 $a,z$ の間の 有効抵抗(effective resistance)$R_{\mathrm{eff}}(a,z)$ とは、$a$ と $z$ に電位差をかけたとき回路全体が 1 本の抵抗としてふるまう、その抵抗の値である。回路網の上のランダムウォークは、各頂点から出る辺をコンダクタンスに比例する確率で選んで進む。電位は「$a$ に先に着く確率」という調和関数であり、有効抵抗は、$a$ の重み $c_a$ と「$a$ を出発して $a$ に戻る前に $z$ に着く確率」の積の逆数で表される。こうして、ランダムウォークの確率の問題が、直列・並列の法則やエネルギー最小の原理のような回路の計算に置き換わる。
この置き換えの強みは単調性にある。辺の抵抗を大きくすると有効抵抗は増える(Rayleigh の単調性原理)。確率を直接比べるのは難しくても、回路を単純なものと比べれば上下から評価できる。その代表的な応用が、無限グラフの上のランダムウォークが出発点に戻るかどうか(再帰性)の判定である。
この記事では、調和関数と電位、Kirchhoff の法則と流れ、有効抵抗とその確率的な意味を定義し、Thomson の原理・Dirichlet の原理・Rayleigh の単調性原理、往復時間の公式 $E_a\tau_z+E_z\tau_a=2R_{\mathrm{eff}}(a,z)\sum_ec_e$ を証明する。後半では無限グラフで有効抵抗を定め、再帰性の判定と Nash-Williams の不等式を証明して、$\mathbb{Z}^2$ の再帰性と二分木の過渡性を導く。

回路網と電位

回路網

$G=(V,E)$ をループも多重辺もない連結グラフとする。各辺 $e=\{x,y\}$ に正の数 $c_e=c_{xy}=c_{yx}$(コンダクタンス)を与え、辺でない組では $c_{xy}=0$ とおく。$r_e=1/c_e$ を辺の 抵抗 という。組 $(G,c)$ を 回路網 という。$G$ が有限のとき有限な回路網という。各頂点 $x$ について $c_x:=\sum_yc_{xy}$ とおき、これが有限であることを仮定する。推移確率
$$ p(x,y)=\frac{c_{xy}}{c_x} $$
の Markov連鎖 $(X_t)_{t\ge0}$ を回路網の上の ランダムウォーク という。すべての $c_e=1$ なら、隣の頂点を等確率で選ぶ単純ランダムウォークである。$X_0=x$ のときの確率と期待値を $P_x$、$E_x$ と書き、頂点の集合 $S$ について $\tau_S:=\min\{t\ge0\mid X_t\in S\}$、$\tau_x^+:=\min\{t\ge1\mid X_t=x\}$ とおく(空集合の最小は $\infty$)。

$c_xp(x,y)=c_{xy}=c_yp(y,x)$ なので、このランダムウォークは $\pi(x)=c_x$ について可逆である。逆に、可逆な Markov 連鎖は $c_{xy}:=\pi(x)p(x,y)$ とおけば回路網の上のランダムウォークになる。

調和関数と電位

関数 $h\colon V\to\mathbb{R}$ が頂点 $x$ で 調和 であるとは
$$ h(x)=\sum_yp(x,y)h(y)=\frac1{c_x}\sum_yc_{xy}h(y) $$
が成り立つことをいう。相異なる 2 頂点 $a,z$ について、$V\setminus\{a,z\}$ のすべての頂点で調和な関数を、$a,z$ の間の 電位(voltage)という。

調和であるとは、値が隣の値の重みつき平均であること、言い換えると Laplacian行列 の重みつき版を当てて $0$ になることである。

電位の存在と一意性

$(G,c)$ を有限な回路網、$a\ne z$ を頂点、$\alpha,\beta\in\mathbb{R}$ とする。$a,z$ の間の電位 $h$ で $h(a)=\alpha$、$h(z)=\beta$ となるものはちょうど 1 つあり、
$$ h(x)=\beta+(\alpha-\beta)P_x(\tau_a< \tau_z) $$
である。特に $\min\{\alpha,\beta\}\le h\le\max\{\alpha,\beta\}$ である。

最大値原理と、先に着く確率

要点:一意性は最大値原理(最大値をとる点の隣も最大値をとる)から、存在は $P_x(\tau_a< \tau_z)$ が最初の 1 歩の条件づけで調和になることから出る。

証明を開く

一意性。 2 つの電位の差 $d$ は電位で、$d(a)=d(z)=0$ である。$M=\max_Vd$ をとる点の集合を $A$ とする。$x\in A\setminus\{a,z\}$ なら $d(x)$ は隣の値の重み正の平均で、どの値も $M$ 以下なので、隣はすべて $A$ に入る。$G$ は連結なので、$A$ の点から $a$ か $z$ へ道をとり、最初に $\{a,z\}$ に着くまでこれをたどると、その点も $A$ に入る。よって $M=0$ である。$-d$ についても同じなので $d=0$ である。

存在。 $g(x):=P_x(\tau_a< \tau_z)$ とおく。有限な連結グラフの上の既約な連鎖は確率 $1$ で $\{a,z\}$ に着くので、$g(a)=1$、$g(z)=0$ である。$x\notin\{a,z\}$ では $\tau_a,\tau_z\ge1$ で、最初の 1 歩で条件をつけると、Markov 性から $g(x)=\sum_yp(x,y)P_y(\tau_a< \tau_z)=\sum_yp(x,y)g(y)$ である。調和性は 1 次結合で保たれ、定数は調和なので、$\beta+(\alpha-\beta)g$ は求める電位である。$0\le g\le1$ から最後の主張が出る。$\square$

流れと Kirchhoff の法則

辺 $\{x,y\}$ ごとに 2 つの向き $xy$、$yx$ を考える。

流れとエネルギー

$a\ne z$ とする。向きのついた辺の上の関数 $\theta$ が $a$ から $z$ への 流れ(flow)であるとは、

  1. $\theta(yx)=-\theta(xy)$(反対称性)、
  2. $x\ne a,z$ なら $\sum_y\theta(xy)=0$(Kirchhoff の節点則)
    が成り立つことをいう。$\|\theta\|:=\sum_y\theta(ay)$ を流れの 強さ といい、強さ $1$ の流れを 単位流 という。流れの エネルギー を
    $$ \mathcal{E}(\theta):=\sum_{e\in E}r_e\,\theta(e)^2 $$
    と定める($\theta(xy)^2=\theta(yx)^2$ なので、向きを忘れて辺ごとに足せばよい)。

反対称性からすべての頂点の流出の和 $\sum_x\sum_y\theta(xy)$ は $0$ なので、$\sum_y\theta(zy)=-\|\theta\|$ である。強さの分だけ $a$ から湧き出し、$z$ で吸い込まれる。

和の入れ替え

$\theta$ を $a$ から $z$ への流れ、$u\colon V\to\mathbb{R}$ を任意の関数とすると
$$ \frac12\sum_{x,y}\theta(xy)\bigl(u(x)-u(y)\bigr)=\|\theta\|\bigl(u(a)-u(z)\bigr). $$

節点則から $\sum_{x,y}\theta(xy)u(x)=\sum_xu(x)\sum_y\theta(xy)=u(a)\|\theta\|-u(z)\|\theta\|$ である。反対称性から $\sum_{x,y}\theta(xy)u(y)=-\sum_{x,y}\theta(yx)u(y)$ で、これは前の和の $-1$ 倍である。差をとって $2$ で割ればよい。$\square$

$v$ を電位とし、各辺で
$$ i(xy):=c_{xy}\bigl(v(x)-v(y)\bigr) $$
とおく。$i$ は反対称で、$x\ne a,z$ では $\sum_yi(xy)=c_xv(x)-\sum_yc_{xy}v(y)=0$(調和性)なので、$a$ から $z$ への流れである。これを $v$ の定める 電流 という。$v(x)-v(y)=r_{xy}\,i(xy)$ が Ohm の法則 であり、閉路 $x_0,x_1,\dots,x_m=x_0$ に沿って $\sum_kr_{x_kx_{k+1}}i(x_kx_{k+1})=\sum_k(v(x_k)-v(x_{k+1}))=0$ となるのが Kirchhoff の 閉路則 である。電流は電位の高い方から低い方へ流れる。

有効抵抗

有効抵抗

有限な回路網の相異なる頂点 $a,z$ について、$v(a)\ne v(z)$ となる電位 $v$ とその電流 $i$ をとり
$$ R_{\mathrm{eff}}(a,z):=\frac{v(a)-v(z)}{\|i\|} $$
を $a,z$ の間の 有効抵抗 という。逆数 $C_{\mathrm{eff}}(a,z)$ を 有効コンダクタンス という。

prop-ern-dirichlet から、電位は $v=\beta+(\alpha-\beta)g$ の形に限るので、$v(a)-v(z)$ と $\|i\|$ はどちらも $\alpha-\beta$ に比例し、比は $v$ の選び方によらない。分母が $0$ でないことは次の命題からわかる。

有効抵抗と脱出確率

有限な回路網の相異なる頂点 $a,z$ について
$$ P_a(\tau_z< \tau_a^+)=\frac1{c_a\,R_{\mathrm{eff}}(a,z)}. $$
さらに、$v(a)-v(z)=1$ となる電位の電流 $i$ のエネルギーは $\mathcal{E}(i)=R_{\mathrm{eff}}(a,z)\|i\|^2$ であり、強さ $1$ に正規化した電流(単位電流)のエネルギーは $R_{\mathrm{eff}}(a,z)$ に等しい。

要点:電位 $v(x)=P_x(\tau_a< \tau_z)$ の電流の強さを、$a$ から出る辺について最初の 1 歩で条件をつけて計算し、エネルギーには lem-ern-summation を使う。

証明を開く

$v(x):=P_x(\tau_a< \tau_z)$ をとると $v(a)=1$、$v(z)=0$ である。最初の 1 歩で条件をつけると$$\|i\|=\sum_yc_{ay}\bigl(1-v(y)\bigr)=c_a\sum_yp(a,y)P_y(\tau_z< \tau_a)=c_aP_a(\tau_z< \tau_a^+)$$である($y=z$ の項では $P_z(\tau_z< \tau_a)=1$)。連結なので $a$ から $z$ への道があり、その道をたどる確率は正なので右辺は正である。$R_{\mathrm{eff}}=1/\|i\|$ から第 1 の式が出る。電位 $v$ の電流 $i$ について、lem-ern-summation を $u=v$ で使うと$$\mathcal{E}(i)=\frac12\sum_{x,y}r_{xy}i(xy)^2=\frac12\sum_{x,y}i(xy)\bigl(v(x)-v(y)\bigr)=\|i\|\bigl(v(a)-v(z)\bigr)=R_{\mathrm{eff}}\|i\|^2$$である($c_{xy}=0$ の組では $i(xy)=0$)。$\square$

直列と並列

直列。 道 $a=x_0,x_1,\dots,x_n=z$ で、辺の抵抗が $r_1,\dots,r_n$ なら、強さ $1$ の電流は各辺に $1$ ずつ流れ、Ohm の法則から $v(a)-v(z)=r_1+\cdots+r_n$ なので $R_{\mathrm{eff}}=\sum_kr_k$ である。並列。 2 頂点だけを結ぶ抵抗 $r_1,\dots,r_n$ の辺を考えるには、多重辺のコンダクタンスを足して 1 本にした回路網を考えればよい。電位差 $1$ のとき電流の強さは $\sum_k1/r_k$ なので $1/R_{\mathrm{eff}}=\sum_k1/r_k$ である。たとえば完全グラフ $K_m$(すべて $c_e=1$)では、対称性から $a,z$ 以外の頂点の電位は等しく、prop-ern-dirichlet の一意性からそれは $\frac12$ である。電流の強さは $1+(m-2)\cdot\frac12=\frac m2$ なので $R_{\mathrm{eff}}(a,z)=\frac2m$ である。

Thomson の原理と Dirichlet の原理

有効抵抗は 2 つの最小化問題の値として表せる。流れの最小化は上からの評価を、関数の最小化は下からの評価を与える。

Thomson の原理

有限な回路網の相異なる頂点 $a,z$ について
$$ R_{\mathrm{eff}}(a,z)=\min\bigl\{\mathcal{E}(\theta)\bigm|\theta\text{ は }a\text{ から }z\text{ への単位流}\bigr\} $$
であり、最小値をとる単位流は単位電流ただ 1 つである。

単位電流との差は交差項を生まない

$i$ を単位電流、$v$ をその電位とし、$\theta$ を任意の単位流とする。$\psi:=\theta-i$ は強さ $0$ の流れである。
$$ \mathcal{E}(\theta)=\mathcal{E}(i)+\mathcal{E}(\psi)+2\sum_{e}r_e\,i(e)\psi(e) $$
で、Ohm の法則と lem-ern-summation($u=v$、流れ $\psi$)から交差項は
$$ \sum_er_ei(e)\psi(e)=\frac12\sum_{x,y}\psi(xy)\bigl(v(x)-v(y)\bigr)=\|\psi\|\bigl(v(a)-v(z)\bigr)=0 $$
である。よって $\mathcal{E}(\theta)=\mathcal{E}(i)+\mathcal{E}(\psi)\ge\mathcal{E}(i)=R_{\mathrm{eff}}$(prop-ern-escape)で、等号は $\mathcal{E}(\psi)=0$、すなわち $\theta=i$ のときに限る。$\square$

回路網の Dirichlet 原理

有限な回路網の相異なる頂点 $a,z$ について、$\mathcal{D}(u):=\sum_{\{x,y\}\in E}c_{xy}\bigl(u(x)-u(y)\bigr)^2$ とおくと
$$ \frac1{R_{\mathrm{eff}}(a,z)}=\min\bigl\{\mathcal{D}(u)\bigm|u\colon V\to\mathbb{R},\ u(a)=1,\ u(z)=0\bigr\} $$
であり、最小値は電位 $v$($v(a)=1$、$v(z)=0$)でとられる。

$v$ の電流を $i$ とすると $\|i\|=1/R_{\mathrm{eff}}$ で、Ohm の法則と prop-ern-escape から $\mathcal{D}(v)=\sum_er_ei(e)^2=R_{\mathrm{eff}}\|i\|^2=1/R_{\mathrm{eff}}$ である。$u(a)=1$、$u(z)=0$ の $u$ を $u=v+w$($w(a)=w(z)=0$)と書くと
$$ \mathcal{D}(u)=\mathcal{D}(v)+\mathcal{D}(w)+2\sum_{\{x,y\}\in E}i(xy)\bigl(w(x)-w(y)\bigr) $$
で、最後の和は lem-ern-summation から $\|i\|(w(a)-w(z))=0$ である。よって $\mathcal{D}(u)\ge\mathcal{D}(v)$ である。$\square$

Rayleigh の単調性原理

同じ有限グラフの上の 2 つのコンダクタンス $c\le c'$(各辺で)について $R_{\mathrm{eff}}(a,z;c)\ge R_{\mathrm{eff}}(a,z;c')$ である。特に、辺を除いても(連結性が保たれる限り)有効抵抗は減らず、$a$ と $z$ を同時には含まない頂点の集合を 1 点に貼り合わせても(生じた多重辺はコンダクタンスを足して 1 本にし、ループは捨てる)有効抵抗は増えない。

各単位流 $\theta$ について $\sum_e\theta(e)^2/c'_e\le\sum_e\theta(e)^2/c_e$ なので、thm-ern-thomson の最小値も同じ向きに比べられる。辺 $e_0$ を除いたグラフの単位流は $e_0$ で $0$ とおけば元のグラフの単位流なので、最小は広い集合でとる元のグラフの方が小さいか等しい。貼り合わせは thm-ern-dirichlet で見る。貼り合わせた回路網の関数は、元のグラフの上で貼り合わせた集合 $S$ で定数な関数と同じで、$\mathcal{D}$ の値も同じである($S$ の中の辺は寄与 $0$、多重辺はコンダクタンスの和で同じ寄与)。最小値を狭い集合でとる貼り合わせた側の $1/R_{\mathrm{eff}}$ は大きいか等しい。$\square$

ブリッジ回路

頂点 $a,b,c,z$ と辺 $ab,ac,bc,bz,cz$(すべて $c_e=1$)の回路網では、$b,c$ を入れ替える写像はグラフの自己同型なので、prop-ern-dirichlet の一意性から電位は $v(b)=v(c)$ である。辺 $bc$ には電流が流れないので、これを除いても同じ電位が電位のままで、$a\!-\!b\!-\!z$ と $a\!-\!c\!-\!z$ の並列になり $R_{\mathrm{eff}}(a,z)=1$ である。辺 $bc$ の抵抗を変えても電位と電流は変わらないので、有効抵抗は $1$ のままである。cor-ern-rayleigh は単調性だけを主張し、狭義の増加までは主張しない。

往復時間の公式

往復時間の公式

有限な回路網の相異なる頂点 $a,z$ について
$$ E_a\tau_z+E_z\tau_a=2R_{\mathrm{eff}}(a,z)\sum_{e\in E}c_e . $$
左辺は $a$ を出発して $z$ に着き、$a$ に戻るまでの時間の期待値(往復時間、commute time)である。

Green 関数を電位として読む

要点:$z$ に着く前に $x$ にいる回数の期待値 $G_z(a,x)$ を $c_x$ で割ったものは電位で、$a$ での値は $R_{\mathrm{eff}}$ である。$a,z$ を入れ替えた電位と足すと定数 $R_{\mathrm{eff}}$ になる。

証明を開く

$G_z(a,x):=E_a\bigl[\#\{t\mid0\le t< \tau_z,\ X_t=x\}\bigr]$($z$ に着く前に $x$ にいる回数の期待値)とおく。有限な既約連鎖では $E_a\tau_z< \infty$ なので有限で、$E_a\tau_z=\sum_xG_z(a,x)$、$G_z(a,z)=0$ である。

調和性。 $x\ne a,z$ とする。$X_0=a\ne x$ なので、$t< \tau_z$ かつ $X_t=x$ となる時刻は $t\ge1$ で、それは「$t-1< \tau_z$、$X_{t-1}=y$、$X_t=x$」となる $y$ がちょうど 1 つあることと同じである($x\ne z$ なので $t-1< \tau_z$ なら $t< \tau_z$)。Markov 性から $G_z(a,x)=\sum_yG_z(a,y)p(y,x)$ で、$c_yp(y,x)=c_{xy}$ を使うと、$\varphi(x):=G_z(a,x)/c_x$ は$$\varphi(x)=\sum_y\frac{G_z(a,y)}{c_y}\cdot\frac{c_{xy}}{c_x}=\sum_yp(x,y)\varphi(y)$$を満たす。よって $\varphi$ は $a,z$ の間の電位である。

境界の値。 $\varphi(z)=0$ である。$a$ を出発して $z$ に着く前に $a$ にいる回数は、成功確率 $P_a(\tau_z< \tau_a^+)$ の幾何分布に従うので、prop-ern-escape から $G_z(a,a)=1/P_a(\tau_z< \tau_a^+)=c_aR_{\mathrm{eff}}$、すなわち $\varphi(a)=R_{\mathrm{eff}}$ である。

和をとる。 $E_a\tau_z=\sum_xc_x\varphi(x)$ である。$a$ と $z$ の役割を替えると、$\psi(x):=G_a(z,x)/c_x$ は $\psi(z)=R_{\mathrm{eff}}$、$\psi(a)=0$ の電位で、prop-ern-dirichlet の一意性から $\psi=R_{\mathrm{eff}}-\varphi$ である。よって$$E_a\tau_z+E_z\tau_a=\sum_xc_x\bigl(\varphi(x)+R_{\mathrm{eff}}-\varphi(x)\bigr)=R_{\mathrm{eff}}\sum_xc_x=2R_{\mathrm{eff}}\sum_ec_e$$である(各辺は両端の $c_x$ に 1 回ずつ数えられる)。$\square$

道と完全グラフ

道。 $n$ 本の辺の道 $0,1,\dots,n$($c_e=1$)では $R_{\mathrm{eff}}(0,n)=n$、$\sum_ec_e=n$ なので往復時間は $2n^2$ である。対称性から $E_0\tau_n=E_n\tau_0=n^2$ で、ギャンブラーの破産の計算と一致する。完全グラフ。 $K_m$ では ex-ern-series-parallel から $R_{\mathrm{eff}}=\frac2m$、$\sum_ec_e=\frac{m(m-1)}2$ で、往復時間は $2(m-1)$ である。実際、各歩で $z$ に進む確率は $\frac1{m-1}$ なので $E_a\tau_z=m-1$ である。

無限グラフと再帰性

$G$ を無限の連結グラフで、各頂点の次数が有限なもの(局所有限)とし、コンダクタンス $c$ を与える。頂点 $a$ を固定し、グラフ距離で $a$ から $n$ 以内の頂点の集合を $B_n$ とする(有限集合である)。$G$ の $B_n$ の外の頂点をすべて 1 点 $z_n$ に貼り合わせ、$B_n$ の外どうしの辺を捨て、$B_n$ と外を結ぶ辺は $z_n$ への辺とする(多重辺はコンダクタンスを足す)。こうしてできる有限な回路網を $G_n$、$R_n:=R_{\mathrm{eff}}(a,z_n;G_n)$ とする。$G_n$ は $G_{n+1}$ で $B_{n+1}\setminus B_n$ を $z_{n+1}$ に貼り合わせたものなので、cor-ern-rayleigh から $R_n\le R_{n+1}$ であり、
$$ R_{\mathrm{eff}}(a,\infty):=\lim_{n\to\infty}R_n\in(0,\infty] $$
が定まる。これを $a$ から無限遠への有効抵抗という。ランダムウォークが確率 $1$ で $a$ に戻るとき 再帰的、そうでないとき 過渡的 という(ランダムウォーク の定義と同じ)。

再帰性の判定

上の設定で
$$ P_a(\tau_a^+=\infty)=\frac1{c_a\,R_{\mathrm{eff}}(a,\infty)}\qquad(1/\infty=0) $$
である。特に、ランダムウォークが再帰的であることと $R_{\mathrm{eff}}(a,\infty)=\infty$ は同値である。

有限の回路網で近似する

要点:$B_n$ を出るまでの歩みは $G_n$ の歩みと同じなので、$B_n$ の外に $a$ へ戻る前に出る確率は $1/(c_aR_n)$ で、$n\to\infty$ でこの事象は $a$ に戻らない事象に減少する。

証明を開く

$G_n$ の上のランダムウォークは、$z_n$ に着くまで $G$ の上のランダムウォークが $B_n$ を出るまでと同じ推移確率で動く($B_n$ の頂点から外への辺のコンダクタンスは $z_n$ への辺にまとめられている)。よって prop-ern-escape から$$P_a\bigl(\tau_{V\setminus B_n}< \tau_a^+\bigr)=\frac1{c_aR_n}$$である。事象 $F_n:=\{\tau_{V\setminus B_n}< \tau_a^+\}$ は $n$ について減少する。$\tau_a^+< \infty$ なら、そこまでの道は有限個の頂点しか通らないので、大きい $n$ で $F_n$ は起きない。逆に $\tau_a^+=\infty$ なのにある $B_n$ に永久にとどまる確率は $0$ である。実際、$B_n$ の各頂点から $a$ への最短の道は $B_n$ の中にあって長さ $n$ 以下なので、$B_n$ のどこにいても $n$ 歩以内に $a$ に着く確率は、$B_n$ の有限個の頂点についての最小値 $\delta>0$ 以上であり、$B_n$ にいる $n$ 歩の区間が $k$ 回続いて $a$ に着かない確率は $(1-\delta)^k$ 以下である。よって $\bigcap_nF_n=\{\tau_a^+=\infty\}$ が確率 $1$ で成り立ち、確率の連続性から左辺は $\lim_n1/(c_aR_n)$ に等しい。$\square$

有限エネルギーの流れによる判定

向きのついた辺の上の反対称な関数 $\theta$ で、$a$ 以外のすべての頂点で節点則を満たし、$\sum_y\theta(ay)=1$ となるものを $a$ から無限遠への単位流という。ランダムウォークが過渡的であることと、エネルギー $\sum_er_e\theta(e)^2$ が有限な $a$ から無限遠への単位流が存在することは同値である。さらに、そのような流れのエネルギーの下限は $R_{\mathrm{eff}}(a,\infty)$ に等しい。

要点:流れを $G_n$ に制限すると $G_n$ の単位流になり、Thomson の原理から $R_n$ はそのエネルギー以下である。逆向きは $G_n$ の単位電流の部分列の極限をとる。

証明を開く

流れがあれば過渡的。 $\theta$ をエネルギー有限の単位流とする。$G_n$ の上で、$B_n$ の中の辺では $\theta$ の値を、$B_n$ の頂点 $x$ から $z_n$ への辺では $x$ と外を結ぶ辺の $\theta$ の和を値とする関数 $\theta_n$ を考えると、$B_n$ の頂点での節点則は保たれ、$\theta_n$ は $a$ から $z_n$ への単位流である($n\ge1$)。Cauchy–Schwarzの不等式 から、まとめた辺のエネルギーはまとめる前の辺のエネルギーの和以下である($(\sum_k\theta_k)^2/\sum_kc_k\le\sum_k\theta_k^2/c_k$)。thm-ern-thomson から $R_n\le\mathcal{E}(\theta_n)\le\mathcal{E}(\theta)$ で、$R_{\mathrm{eff}}(a,\infty)\le\mathcal{E}(\theta)< \infty$ である。thm-ern-recurrence から過渡的である。

過渡的なら流れがある。 $R:=R_{\mathrm{eff}}(a,\infty)< \infty$ とする。$G_n$ の単位電流 $i_n$ を $G$ の辺の上に、$B_n$ の中の辺ではその値、$B_n$ と外を結ぶ辺 $xy$ では $c_{xy}(v_n(x)-v_n(z_n))$($v_n$ は $i_n$ の電位)として戻し、それ以外の辺では $0$ とする。各辺 $e$ で $r_ei_n(e)^2\le\mathcal{E}(i_n)=R_n\le R$ なので $\lvert i_n(e)\rvert\le\sqrt{Rc_e}$ は有界である。辺は可算個なので、対角線論法で部分列 $n_k$ をとり、すべての辺で $i_{n_k}(e)\to\theta(e)$ とできる。各頂点の次数は有限なので、節点則と $\sum_y\theta(ay)=1$ は極限でも成り立つ。有限個の辺の集合 $F$ について $\sum_{e\in F}r_e\theta(e)^2=\lim_k\sum_{e\in F}r_ei_{n_k}(e)^2\le R$ なので、$\mathcal{E}(\theta)\le R$ である。前半とあわせて下限が $R$ であることも出る。$\square$

Nash-Williams の不等式

有限な回路網の相異なる頂点 $a,z$ について、辺の集合 $\Pi$ が $a$ と $z$ を 分ける とは、$a$ から $z$ へのどの道も $\Pi$ の辺を通ることをいう。互いに素な辺の集合 $\Pi_1,\dots,\Pi_m$ がどれも $a$ と $z$ を分けるなら
$$ R_{\mathrm{eff}}(a,z)\ge\sum_{k=1}^m\Bigl(\sum_{e\in\Pi_k}c_e\Bigr)^{-1}. $$

切断を通る流れと Cauchy–Schwarz

要点:単位流は各切断を合計 $1$ 以上通り、Cauchy–Schwarzの不等式 で切断ごとのエネルギーが $(\sum_{e\in\Pi_k}c_e)^{-1}$ 以上になる。足して Thomson の原理を使う。

証明を開く

切断を通る量。 $\theta$ を単位流、$\Pi$ を $a$ と $z$ を分ける辺の集合とし、$S$ を $\Pi$ の辺を使わずに $a$ から行ける頂点の集合とする($z\notin S$)。節点則から $\sum_{x\in S}\sum_y\theta(xy)=\|\theta\|=1$ で、$S$ の中どうしの辺の寄与は反対称性で打ち消し合うので、$\sum_{x\in S,\,y\notin S}\theta(xy)=1$ である。$x\in S$、$y\notin S$ の辺は $\Pi$ に属する(そうでなければ $y\in S$)ので、$\sum_{e\in\Pi}\lvert\theta(e)\rvert\ge1$ である。

評価。 Cauchy–Schwarzの不等式 から$$1\le\Bigl(\sum_{e\in\Pi_k}\sqrt{c_e}\cdot\sqrt{r_e}\,\lvert\theta(e)\rvert\Bigr)^2\le\sum_{e\in\Pi_k}c_e\cdot\sum_{e\in\Pi_k}r_e\theta(e)^2$$である。$\Pi_k$ は互いに素なので $\mathcal{E}(\theta)\ge\sum_k\sum_{e\in\Pi_k}r_e\theta(e)^2\ge\sum_k(\sum_{e\in\Pi_k}c_e)^{-1}$ で、thm-ern-thomson から主張が出る。$\square$

$\mathbb{Z}^2$ は再帰的

$\mathbb{Z}^2$(隣接する格子点を結び、$c_e=1$)で $a=0$ とする。$k\ge0$ について、$\max\{\lvert x_1\rvert,\lvert x_2\rvert\}=k$ の点と $k+1$ の点を結ぶ辺の集合を $\Pi_k$ とすると、$\lvert\Pi_k\rvert=8k+4$ である(正方形の 4 辺に $2k+1$ 本ずつ)。$k\le n/2-1$ なら $\Pi_k$ の辺の両端はグラフ距離 $2k+2\le n$ 以内にあって $G_n$ の辺であり、$0$ から $B_n$ の外への道は必ず $\Pi_k$ を横切るので、$\Pi_k$ は $G_n$ で $0$ と $z_n$ を分ける。thm-ern-nash-williams から
$$ R_n\ge\sum_{k=0}^{\lfloor n/2\rfloor-1}\frac1{8k+4}\longrightarrow\infty $$
で、thm-ern-recurrence から $\mathbb{Z}^2$ の単純ランダムウォークは再帰的である。和は $\frac18\log n$ の程度でしか増えず、再帰性がきわどいことを表している。

二分木は過渡的

根 $a$ から各頂点が 2 つの子をもつ無限の木($c_e=1$)を考える。$B_n$ は深さ $n$ 以下の頂点で、$G_n$ では深さ $n$ の頂点から子への辺が $z_n$ への辺になる。深さ $k-1$ と $k$ を結ぶ $2^k$ 本の辺の集合 $\Pi_k$($1\le k\le n+1$)はどれも $G_n$ で根と $z_n$ を分けるので、Nash-Williams の不等式から $R_n\ge\sum_{k=1}^{n+1}2^{-k}$ である。逆に、各頂点で流れを 2 つの子に半分ずつ分ける単位流は深さ $k$ の辺に $2^{-k}$ ずつ流れ、$G_n$ でのエネルギーは $\sum_{k=1}^{n+1}2^k\cdot4^{-k}$ である。よって $R_n=1-2^{-(n+1)}$、$R_{\mathrm{eff}}(a,\infty)=1$ で、thm-ern-recurrence から根に戻らない確率は $\frac1{c_aR}=\frac12$ である。

$\mathbb{Z}^d$($d\ge3$)の過渡性は ランダムウォーク の定理「Pólya の定理」が積分表示で証明している。回路網の方法では、原点から放射状に広がるエネルギー有限の流れを作って thm-ern-flow-criterion を当てる(Gri18 Theorem 1.32 の証明、pp. 14–16)。

反例:仮定を外すと成り立たないこと

各行は、その主張の仮定を 1 つだけ外す。

主張外す仮定反例成り立たなくなること
prop-ern-dirichletグラフの有限性整数全体の道 $\mathbb{Z}$($c_e=1$)、$a=0$、$z=1$$h_1(x)=1$($x\ge1$)・$0$($x\le0$)と $h_2(x)=\max\{x,0\}$ はどちらも電位で境界の値も等しいが、$h_1\ne h_2$
prop-ern-dirichlet連結性頂点 $a,z,u,w$、辺 $az$ と $uw$ だけ$u,w$ で同じ定数をとる関数はどれも電位で、境界の値だけでは決まらない
thm-ern-thomson節点則道 $a\!-\!u\!-\!z$($c_e=1$)、$\theta(au)=1$、$\theta(uz)=0$$\sum_y\theta(ay)=1$ の反対称な関数で、エネルギー $1$ が $R_{\mathrm{eff}}=2$ を下回る
thm-ern-nash-williams切断が互いに素1 本の辺 $az$($c_e=1$)、$\Pi_1=\Pi_2=\{az\}$右辺は $2$ になり、$R_{\mathrm{eff}}=1$ を上回る
表の確かめ

1 行目:$h_2$ は $x\ge2$ で $\frac12((x-1)+(x+1))=x$、$x\le-1$ で $0$ なので、$0,1$ 以外のすべての点で調和である。$h_1$ も同様である。prop-ern-dirichlet の証明の最大値原理は、最大値をとる点が存在することに有限性を使っている。2 行目:$u$ の隣は $w$ だけなので、$h(u)=h(w)$ なら $u,w$ で調和である。3 行目:$u$ で $\theta(ua)+\theta(uz)=-1\ne0$ なので節点則を満たさない。直列の法則(ex-ern-series-parallel)から $R_{\mathrm{eff}}=2$ である。4 行目は自明である。$\square$

確率を直接比べることはできない

cor-ern-rayleigh は有効抵抗の単調性であり、戻る確率の単調性ではない。thm-ern-recurrence の戻らない確率 $1/(c_aR_{\mathrm{eff}}(a,\infty))$ は $c_a$ にもよるので、$a$ に接する辺を除くと $c_a$ が減って戻らない確率が増えることがある。たとえば ex-ern-binary-tree の根 $\rho$ に新しい頂点 $a$ を辺で結び、さらに $a$ に行き止まりの頂点 $u$(隣は $a$ だけ)を結ぶ($c_e=1$)。$u$ の電位は $a$ の電位に等しく辺 $au$ に電流は流れないので、$R_{\mathrm{eff}}(a,\infty)=1+1=2$ で、$c_a=2$ から戻らない確率は $\frac14$ である。辺 $au$ を除くと有効抵抗は $2$ のままだが $c_a=1$ になり、戻らない確率は $\frac12$ に増える。一方、$a$ に接しない辺のコンダクタンスを小さくしても $c_a$ は変わらず、各 $R_n$ は減らないので、戻る確率は減らない。

補足

名前と文献

電位・流れ・有効抵抗の定義、脱出確率の公式、直列・並列の法則、Thomson の原理、Rayleigh の単調性原理、Dirichlet の原理、往復時間の公式、無限グラフでの判定、Nash-Williams の不等式は Nac20 の第 2 章にある(Claim 2.22 p. 18、Lemma 2.26 p. 21、Theorem 2.28 p. 23、Corollary 2.29・Lemma 2.32 p. 24、Corollary 2.39・Theorem 2.42 p. 27)。Gri18 の第 1 章は同じ理論を Kirchhoff の法則から始めて述べ(Theorem 1.28・1.29 pp. 9–10)、再帰性の判定(Theorem 1.30・Corollary 1.31 p. 11)と Pólya の定理の回路網による証明(Theorem 1.32 pp. 14–16)を与える。Kirchhoff の法則の解が全域木の数え上げで書けること(Kirchhoff 1847)も同書 Theorem 1.16(p. 6)にあり、Kirchhoffの行列木定理 と同じ源をもつ。

関連項目

参考文献

[1]
Asaf Nachmias, Planar Maps, Random Walks and Circle Packing — École d'Été de Probabilités de Saint-Flour XLVIII - 2018, Lecture Notes in Mathematics 2243, Springer, 2020, Chapter 2:Claim 2.22(p. 18)、Lemma 2.26(p. 21)、Theorem 2.28(p. 23)、Corollary 2.29・Lemma 2.32(p. 24)、Corollary 2.39・Theorem 2.42(p. 27)
[2]
Geoffrey Grimmett, Probability on Graphs: Random Processes on Graphs and Lattices, 2nd ed., Cambridge University Press, 2018, Chapter 1:Theorem 1.16(p. 6)、Theorem 1.28・1.29(pp. 9–10)、Theorem 1.30・Corollary 1.31(p. 11)、Theorem 1.32(pp. 14–16)

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する