ループ消去ランダムウォーク

同義語:loop-erased random walkLERW

概要

ループ消去ランダムウォーク(loop-erased random walk)とは、ランダムウォークの歩みから同じ頂点に戻るループをできた順に消して得られる単純な道で、Lawler が導入した。有限グラフ上で頂点 $a$ から集合 $B$ に着くまでの歩みを消去したものが特定の道をとる確率は、推移確率の積と、道に沿って狭まる領域の Green 関数の値の積に等しく、行列式の比にも書ける。この公式から、可逆な酔歩では始点と終点を入れ替えても分布が変わらないこと、次の一歩がまだ通っていない点への調和関数に比例して選ばれることが従う。Wilson のアルゴリズムで一様全域木を作る部品であり、平面格子の尺度極限は放射型 $\mathrm{SLE}_2$ である。

$$\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連鎖, ランダムウォーク, 行列式

ループ消去ランダムウォーク(loop-erased random walk、LERW)とは、ランダムウォークの歩みから、ループ(同じ頂点に戻ってくる部分)をできた順に消して得られる単純な道(同じ頂点を 2 度通らない道)である。Lawler が導入した(LSW04 p. 4)。歩みは同じ頂点を何度も訪れるが、消去の後には「ある頂点から出発して、ある集合に着くまでの単純な道」が残る。
LERW は 自己回避歩行 のように単純な道を無作為に選ぶが、道を一様に選ぶのではなく、背後にあるランダムウォークの分布を受け継ぐ。そのため分布を明示的に書ける。この記事の主定理(thm-lerw-formula)は、LERW が特定の道 $\gamma$ をとる確率が、推移確率の積と、少しずつ狭まる領域の Green 関数の値の積で書けることである。これを行列式に書き直すと、始点と終点を入れ替えても分布が変わらないこと(thm-lerw-reversal)と、LERW が「まだ通っていない頂点への調和関数」に従って一歩ずつ進むこと(prop-lerw-laplacian)が従う。

結果内容この記事での扱い
thm-lerw-formula道の確率は推移確率と Green 関数の積証明する
prop-lerw-det行列式による書き換え証明する
thm-lerw-reversal可逆な酔歩では向きを逆にしても同じ分布証明する
prop-lerw-laplacian領域 Markov 性と、調和関数による推移証明する
prop-lerw-transient過渡的な歩みの消去証明する
rem-lerw-scaling平面格子での尺度極限と歩数主張だけ

定義

以下、$G=(V,E)$ はループのない連結グラフで、辺に正の重み(コンダクタンス)$c_e$ がある。$c_x:=\sum_yc_{xy}$ とし、$p(x,y):=c_{xy}/c_x$ を推移確率とする酔歩(回路網のランダムウォーク)を $(X_n)$、$X_0=x$ のときの確率を $P_x$ と書く。すべての $c_e=1$ なら単純ランダムウォークである。頂点の集合 $S$ について $\tau_S:=\min\{n\ge0\mid X_n\in S\}$ とおく。
頂点の列 $w=(w_0,\dots,w_k)$ で隣り合う 2 項が隣接するものを 歩み という。

ループ消去

歩み $w=(w_0,\dots,w_k)$ について、道 $\gamma$ を次のように作る。$\gamma=(w_0)$ から始め、$i=1,\dots,k$ の順に、$w_i$ が $\gamma$ に現れなければ $\gamma$ の末尾に $w_i$ を付け加え、$\gamma=(\gamma_0,\dots,\gamma_l)$ の $\gamma_j$ に等しければ $\gamma$ を $(\gamma_0,\dots,\gamma_j)$ に切り詰める。最後に得られる単純な道を $w$ の ループ消去 といい、$\mathrm{LE}(w)$ と書く。

$\mathrm{LE}(w)$ は $w_0$ から $w_k$ への単純な道で、各段階で $\gamma$ の末尾はつねに $w_i$ である。たとえば $w=(a,x,a,y,x,b)$ では、$\gamma$ は $(a)\to(a,x)\to(a)\to(a,y)\to(a,y,x)\to(a,y,x,b)$ と変わる。

ループ消去ランダムウォーク

$G$ が有限で、$B\subset V$ が空でなく $a\in V\setminus B$ とする。酔歩は確率 $1$ で $B$ に着くので、$\mathrm{LE}\bigl(X_0,\dots,X_{\tau_B}\bigr)$($X_0=a$)が定まる。この無作為な単純な道を、$a$ から $B$ への ループ消去ランダムウォーク という。$B=\{b\}$ のときは $a$ から $b$ への LERW という。

LERW は $a$ から出発し、$B$ の点に初めて着いたところで終わる単純な道で、その最後の一歩は歩みの最後の一歩 $X_{\tau_B-1}\to X_{\tau_B}$ に等しい(末尾の点はつねに付け加えられ、$B$ の点はそれまで現れないからである)。

閉路の上の LERW

$m\ge3$ とし、閉路 $C_m$(頂点 $\mathbb Z/m$)の単純ランダムウォークを $0$ から出発させ、$b$($0< b< m$)に着くまでの LERW を考える。$C_m$ の $0$ から $b$ への単純な道は、時計回りの弧 $(0,1,\dots,b)$ と反時計回りの弧 $(0,m-1,\dots,b)$ の 2 本である。LERW の最後の一歩は歩みの最後の一歩なので、LERW が時計回りの弧になるのは、歩みが $b-1$ の側から $b$ に着くときである。$C_m$ の歩みを $\mathbb Z$ に持ち上げると、これは $0$ から出発した $\mathbb Z$ の単純ランダムウォークが $b-m$ より先に $b$ に着く事象で、確率は破産問題の公式から $\frac{0-(b-m)}{b-(b-m)}=\frac{m-b}m$ である。したがって
$$ P\bigl(\text{LERW}=(0,1,\dots,b)\bigr)=\frac{m-b}m $$
で、近い側の弧ほど選ばれやすい。

道の確率の公式

$A\subsetneq V$ と $x,y\in A$ について、$A$ の外に出るまでの訪問回数の期待値
$$ G_A(x,y):=E_x\Bigl[\#\{n< \tau_{V\setminus A}\mid X_n=y\}\Bigr]=\sum_{n\ge0}P_x\bigl(X_n=y,\ n< \tau_{V\setminus A}\bigr) $$
を、$A$ の Green 関数($A$ の外で止めた酔歩の Green 関数)という。$P_A:=(p(x,y))_{x,y\in A}$ とおくと $P_x(X_n=y,\ n< \tau_{V\setminus A})=(P_A^n)_{xy}$ である。$G$ が有限で連結なら、どの $x\in A$ からも $|A|$ 歩以内に $A$ の外に出る道があるので、ある $\theta< 1$ について $P_x(\tau_{V\setminus A}>n|A|)\le\theta^n$ となり、級数は収束して
$$ G_A=\sum_{n\ge0}P_A^n=(I-P_A)^{-1} $$
である。
まず、ループ消去の結果を歩みの分解で言い表す。

歩みの分解

$B\subset V$ とし、歩み $w=(w_0,\dots,w_k)$ は $w_i\notin B$($i< k$)、$w_k\in B$ を満たすとする。単純な道 $\gamma=(\gamma_0,\dots,\gamma_m)$($m\ge1$)が $\gamma_0=w_0$、$\gamma_0,\dots,\gamma_{m-1}\notin B$、$\gamma_m\in B$ を満たすとき、$A_j:=V\setminus(B\cup\{\gamma_0,\dots,\gamma_{j-1}\})$($0\le j< m$)とおく。このとき $\mathrm{LE}(w)=\gamma$ であることと、$w$ が
$$ w=\ell_0\oplus(\gamma_0\to\gamma_1)\oplus\ell_1\oplus(\gamma_1\to\gamma_2)\oplus\cdots\oplus\ell_{m-1}\oplus(\gamma_{m-1}\to\gamma_m) $$
と書けることは同値である。ここで $\ell_j$ は $\gamma_j$ から $\gamma_j$ への歩み(長さ $0$ でもよい)で頂点がすべて $A_j$ に入るもの、$\oplus$ は歩みのつなぎ、$(\gamma_j\to\gamma_{j+1})$ は一歩である。この書き方はあれば一意である。

最後に始点を出た時刻で切る

$m$ についての帰納法で示す。$\sigma:=\max\{i< k\mid w_i=w_0\}$ とおく。
消去は $\sigma$ の後の部分だけで決まる. 時刻 $\sigma$ で $w_\sigma=w_0$ は $\gamma$ の先頭にあるので、$\gamma$ は $(w_0)$ に切り詰められる。$\sigma$ の後 $w_0$ は現れないので、以後の切り詰めは先頭の $w_0$ を消さず、$w_0$ を除いた部分の操作は歩み $w':=(w_{\sigma+1},\dots,w_k)$ のループ消去と同じである。よって
$$ \mathrm{LE}(w)=(w_0)\oplus\mathrm{LE}(w') $$
であり、$\mathrm{LE}(w')$ は $w_{\sigma+1}$ から始まる。
帰納法. したがって $\mathrm{LE}(w)=\gamma$ は、$w_{\sigma+1}=\gamma_1$ かつ $\mathrm{LE}(w')=(\gamma_1,\dots,\gamma_m)$ と同値である。$w'$ は $\gamma_0$ を通らず、$B':=B\cup\{\gamma_0\}$ に初めて着くのが最後の時刻で、その点は $B$ にある。$m=1$ なら $\gamma_1\in B$ なので $w'=(\gamma_1)$、すなわち $\sigma=k-1$ である。$m\ge2$ なら、$w'$ と道 $(\gamma_1,\dots,\gamma_m)$ と $B'$ に帰納法の仮定を当てると、$w'$ は $\ell_1\oplus(\gamma_1\to\gamma_2)\oplus\cdots$ と分解され、$\ell_j$ の頂点は $V\setminus(B'\cup\{\gamma_1,\dots,\gamma_{j-1}\})=A_j$ に入る。$\ell_0:=(w_0,\dots,w_\sigma)$ の頂点は $V\setminus B=A_0$ に入る。
逆に $w$ がこの形に書けるとき、$\ell_0$ の後の部分は $\gamma_0$ を通らない($\ell_j$($j\ge1$)は $A_j\not\ni\gamma_0$ に入り、一歩の行き先 $\gamma_{j+1}$ も $\gamma_0$ でない)ので、$\ell_0$ の終わりは $\sigma$ である。よって上の議論が逆にたどれて $\mathrm{LE}(w)=\gamma$ であり、$\ell_0$ が $\sigma$ で決まることから、帰納的に分解は一意である。$\square$

道の確率の公式

$G$ を有限連結グラフ、$B\subset V$ を空でない集合、$a\in V\setminus B$ とする。単純な道 $\gamma=(\gamma_0,\dots,\gamma_m)$ で $\gamma_0=a$、$\gamma_0,\dots,\gamma_{m-1}\notin B$、$\gamma_m\in B$ を満たすものについて、$A_j:=V\setminus(B\cup\{\gamma_0,\dots,\gamma_{j-1}\})$ とおくと
$$ P_a\Bigl(\mathrm{LE}\bigl(X_0,\dots,X_{\tau_B}\bigr)=\gamma\Bigr)=\prod_{j=0}^{m-1}p(\gamma_j,\gamma_{j+1})\cdot\prod_{j=0}^{m-1}G_{A_j}(\gamma_j,\gamma_j) $$
である。

分解に沿って和をとる

歩み $w$ が $X_0,\dots,X_{\tau_B}$ として現れる確率は $p(w):=\prod_ip(w_i,w_{i+1})$ である。lem-lerw-decomp により、$\mathrm{LE}=\gamma$ となる歩みは、ループの組 $(\ell_0,\dots,\ell_{m-1})$ と 1 対 1 に対応し、$p(w)=\prod_jp(\ell_j)\cdot\prod_jp(\gamma_j,\gamma_{j+1})$ である。$\ell_j$ は互いに独立に選べるので、和は積に分かれ、
$$ \sum_{\ell_j}p(\ell_j)=\sum_{n\ge0}P_{\gamma_j}\bigl(X_n=\gamma_j,\ X_i\in A_j\ (i\le n)\bigr)=G_{A_j}(\gamma_j,\gamma_j) $$
である(和は $\ell_j$ の長さ $n$ ごとにまとめた)。$\gamma_j\in A_j$ なので右辺は定義どおりの Green 関数の値である。$\square$

$A_j$ は $j$ とともに 1 点ずつ狭くなる。LERW がすでに通った点は、その後のループが訪れられない点として領域から除かれる。

行列式と向きの対称性

$S\subset V$ について $D(S):=\det\bigl(I-P_S\bigr)$($S=\emptyset$ なら $D(\emptyset)=1$)とおく。$S\ne V$ なら $I-P_S$ は逆行列 $G_S$ をもつので $D(S)\ne0$ である。

行列式による書き換え

thm-lerw-formula の記号で、道 $\gamma$ の頂点の集合も $\gamma$ と書くと
$$ \prod_{j=0}^{m-1}G_{A_j}(\gamma_j,\gamma_j)=\frac{D\bigl(V\setminus(B\cup\gamma)\bigr)}{D(V\setminus B)},\qquad P_a(\mathrm{LE}=\gamma)=p(\gamma)\,\frac{D\bigl(V\setminus(B\cup\gamma)\bigr)}{D(V\setminus B)} $$
である。ここで $p(\gamma):=\prod_jp(\gamma_j,\gamma_{j+1})$ である。とくに Green 関数の積は、$\gamma$ の頂点をたどる順序によらない。

余因子で 1 点ずつ外す

$A\subsetneq V$、$x\in A$ について、$G_A=(I-P_A)^{-1}$ の対角成分は Cramerの公式 により
$$ G_A(x,x)=\frac{\det\bigl(I-P_{A\setminus\{x\}}\bigr)}{\det(I-P_A)}=\frac{D(A\setminus\{x\})}{D(A)} $$
である($(x,x)$ 余因子は $x$ の行と列を除いた行列式)。$A_{j+1}=A_j\setminus\{\gamma_j\}$ なので積は望遠鏡のように打ち消し合い、$D(A_m)/D(A_0)$ が残る。$A_0=V\setminus B$ で、$\gamma_m\in B$ から $A_m=V\setminus(B\cup\gamma)$ である。$\square$

向きを逆にしても分布は同じ

$G$ を有限連結グラフ、$a\ne b$ を頂点とする。$a$ から $b$ への LERW の向きを逆にした道は、$b$ から $a$ への LERW と同じ分布をもつ。すなわち、$a$ から $b$ への単純な道 $\gamma$ とその逆 $\gamma^{\mathrm{rev}}:=(\gamma_m,\dots,\gamma_0)$ について
$$ P_a\bigl(\mathrm{LE}(X_0,\dots,X_{\tau_b})=\gamma\bigr)=P_b\bigl(\mathrm{LE}(X_0,\dots,X_{\tau_a})=\gamma^{\mathrm{rev}}\bigr) $$
である。

比が道によらないことを示す

prop-lerw-det を $B=\{b\}$ と $B=\{a\}$ に当てる。どちらでも $B\cup\gamma$ は $\gamma$ の頂点の集合に等しいので、
$$ \frac{P_a(\mathrm{LE}=\gamma)}{P_b(\mathrm{LE}=\gamma^{\mathrm{rev}})}=\frac{p(\gamma)}{p(\gamma^{\mathrm{rev}})}\cdot\frac{D(V\setminus\{a\})}{D(V\setminus\{b\})} $$
である。$p(\gamma)=\prod_jc_{\gamma_j\gamma_{j+1}}/c_{\gamma_j}$、$p(\gamma^{\mathrm{rev}})=\prod_jc_{\gamma_j\gamma_{j+1}}/c_{\gamma_{j+1}}$ なので、$p(\gamma)/p(\gamma^{\mathrm{rev}})=c_{\gamma_m}/c_{\gamma_0}=c_b/c_a$ である。よって比は $\gamma$ によらない定数 $\kappa>0$ である。$\gamma\mapsto\gamma^{\mathrm{rev}}$ は $a$ から $b$ への単純な道と $b$ から $a$ への単純な道の全単射で、両辺をすべての $\gamma$ について足すとどちらも $1$ になる(LERW は確率 $1$ でどれかの道に等しい)。したがって $\kappa=1$ である。$\square$

証明の副産物として $c_b\,D(V\setminus\{a\})=c_a\,D(V\setminus\{b\})$ が得られる。また thm-lerw-reversal は 一様全域木 からも読み取れる。同記事の系「木の中の道」により、$a$ から $b$ への LERW は重みつき全域木の中で $a$ と $b$ を結ぶ道と同じ分布をもち、木の中の道は向きを逆にすれば $b$ から $a$ への道だからである。上の証明は木を使わず、公式だけから示した。
対称性は分布についての主張で、歩みごとには成り立たない。$a,x,y,b$ を頂点とする完全グラフ $K_4$ の歩み $w=(a,x,a,y,x,b)$ では $\mathrm{LE}(w)=(a,y,x,b)$ だが、逆の歩み $(b,x,y,a,x,a)$ のループ消去は $(b,x,a)$ で、その逆 $(a,x,b)$ は $\mathrm{LE}(w)$ と異なる。

領域 Markov 性と調和関数による推移

LERW の最初の何歩かが決まったとき、残りの部分は「すでに通った点を避けて $B$ に着く」という条件をつけた LERW になる。

領域 Markov 性と Laplace 酔歩

thm-lerw-formula の状況で、$\eta=(\eta_0,\dots,\eta_j)$($\eta_0=a$、$\eta_0,\dots,\eta_j\notin B$)を LERW の最初の $j+1$ 頂点がとりうる単純な道とし、$B':=B\cup\{\eta_0,\dots,\eta_{j-1}\}$ とおく。LERW を $(\Gamma_0,\Gamma_1,\dots)$ と書く。

  1. $(\Gamma_0,\dots,\Gamma_j)=\eta$ のもとで、残りの部分 $(\Gamma_j,\Gamma_{j+1},\dots)$ の条件つき分布は、$\eta_j$ から出発し $B'$ に着くまで走らせた歩みのループ消去の、$X_{\tau_{B'}}\in B$ という条件のもとでの分布に等しい。
  2. $h_\eta(y):=P_y\bigl(\tau_B< \tau_{\{\eta_0,\dots,\eta_j\}}\bigr)$ とおく($y\in B$ なら $1$、$y$ が $\eta$ の頂点なら $0$)。このとき
    $$ P\bigl(\Gamma_{j+1}=y\mid(\Gamma_0,\dots,\Gamma_j)=\eta\bigr)=\frac{p(\eta_j,y)\,h_\eta(y)}{\sum_zp(\eta_j,z)\,h_\eta(z)} $$
    である。
公式を前半と後半に分ける

1. $\gamma$ を $\eta$ で始まる道とする。thm-lerw-formula の積を $i< j$ と $i\ge j$ に分けると、$i\ge j$ の $A_i=V\setminus(B'\cup\{\gamma_j,\dots,\gamma_{i-1}\})$ なので、後半の積は $\eta_j$ から $B'$ まで走らせた歩みのループ消去が $(\gamma_j,\dots,\gamma_m)$ になる確率の公式そのものである。よって
$$ P_a(\mathrm{LE}=\gamma)=C(\eta)\,P_{\eta_j}\Bigl(\mathrm{LE}\bigl(X_0,\dots,X_{\tau_{B'}}\bigr)=(\gamma_j,\dots,\gamma_m)\Bigr) $$
で、$C(\eta):=\prod_{i< j}p(\eta_i,\eta_{i+1})G_{A_i}(\eta_i,\eta_i)$ は $\eta$ だけで決まる。$\gamma$ の後半は、$B'$ の中でも $B$ の点で終わる道を動く。これを $\gamma$ について足せば $P(\text{最初の }j+1\text{ 頂点}=\eta)=C(\eta)P_{\eta_j}(X_{\tau_{B'}}\in B)$ で、割れば 1 を得る。
2. 1 により、$\eta_j$ から $B'$ まで走らせた歩み($\eta_j\notin B'$)のループ消去の 2 番目の頂点が $y$ で、終点が $B$ にある確率を求めればよい。同じく公式を最初の一歩とその後に分けると、それは
$$ p(\eta_j,y)\,G_{A_j}(\eta_j,\eta_j)\,P_y\bigl(X_{\tau_{B''}}\in B\bigr),\qquad B'':=B'\cup\{\eta_j\} $$
である($y\in B$ なら最後の因子は $1$、$y\in B'\setminus B$ なら道は $B$ で終わらないので $0$)。$P_y(X_{\tau_{B''}}\in B)=h_\eta(y)$ であり、$G_{A_j}(\eta_j,\eta_j)$ は $y$ によらないので、正規化すれば主張を得る。$\square$

$h_\eta$ は、$B$ で $1$、すでに通った点で $0$ の値をとり、残りの頂点では $h(x)=\sum_yp(x,y)h(y)$ を満たす調和関数である。LERW は、次の一歩をこの調和関数の値に比例する確率で選ぶ。このように、過去の道全体で決まる調和関数に従って進む過程を Laplace 酔歩(Laplacian random walk)という。LERW の次の一歩は現在の点だけでは決まらず、過去の道全体による。

無限グラフの上の LERW

無限グラフでは歩みを止めずに走らせ、道全体のループを消すことを考える。

過渡的な歩みのループ消去

無限の歩み $w=(w_0,w_1,\dots)$ がどの頂点も有限回しか訪れないとする。$\sigma_0:=\max\{i\mid w_i=w_0\}$、$\gamma_0:=w_0$ とし、帰納的に
$$ \gamma_{i+1}:=w_{\sigma_i+1},\qquad\sigma_{i+1}:=\max\{n\mid w_n=\gamma_{i+1}\} $$
とおく。このとき $\gamma=(\gamma_0,\gamma_1,\dots)$ は無限の単純な道で、各 $i$ と $n>\sigma_i$ について、$\mathrm{LE}(w_0,\dots,w_n)$ の最初の $i+1$ 頂点は $(\gamma_0,\dots,\gamma_i)$ である。

要点:始点を最後に出た時刻で切ると、残りの歩みの消去に帰着する。

詳細

$\sigma_{i+1}\ge\sigma_i+1>\sigma_i$ である。$k\le i$ について $\gamma_k$ は時刻 $\sigma_k\le\sigma_i$ の後に現れないが、$\gamma_{i+1}$ は時刻 $\sigma_i+1$ に現れるので、$\gamma_{i+1}\ne\gamma_k$ であり、$\gamma$ は単純な道である。

後半は $i$ についての帰納法で示す。prf-lerw-decomp の前半と同じく、時刻 $\sigma_0$ で消去中の道は $(w_0)$ に切り詰められ、その後 $w_0$ は現れないので、$n>\sigma_0$ では $\mathrm{LE}(w_0,\dots,w_n)=(w_0)\oplus\mathrm{LE}(w_{\sigma_0+1},\dots,w_n)$ である。右辺の歩みは $\gamma_1$ から始まり、どの頂点も有限回しか訪れず、その $\sigma$ に当たる時刻は $\sigma_1,\sigma_2,\dots$(から $\sigma_0+1$ を引いたもの)である。これに帰納法の仮定を当てればよい。$\square$

$\mathbb Z^d$($d\ge3$)の単純ランダムウォークは過渡的で、確率 $1$ でどの点も有限回しか訪れない(ランダムウォーク の Pólya の定理と系「原点に戻る回数」を、平行移動と強 Markov 性で各点に当てる)。よって prop-lerw-transient の $\gamma$ が確率 $1$ で定まり、これを $\mathbb Z^d$ の 無限 LERW という。$d=1,2$ では歩みは確率 $1$ で原点に無限回戻るので $\sigma_0$ が定まらず、この定義は使えない。平面では、有界な領域の中で、境界に着くまでの LERW を扱う。

平面格子での尺度極限と歩数

$D\subsetneq\mathbb C$ を $0$ を含む単連結領域とし、$\delta\mathbb Z^2$ の単純ランダムウォークを $0$ から出発させ $D$ の境界に着くまで走らせたときの LERW の分布を $\mu_\delta$ とする。$\delta\to0$ で $\mu_\delta$ は、単位円板から $D$ への $0$ を固定する等角写像による放射型 $\mathrm{SLE}_2$ の道の像の分布に弱収束する(Lawler–Schramm–Werner、LSW04 Theorem 1.1、p. 7)。この収束は Schramm が予想し、尺度極限の等角不変性と同値であることを示していた(LSW04 p. 4。Schramm–Loewner発展 を参照)。また Kenyon は、$\mathbb Z^2$ の $N\times N$ の正方形の 2 つの隅を結ぶ LERW の歩数の期待値が $N^{5/4}$ の程度であることを示した(LSW04 p. 6)。この記事ではどちらも証明しない。

一様全域木との関係

LERW は全域木を無作為に選ぶ手順の部品になる。根を固定し、まだ木に入っていない頂点から酔歩を走らせて木に着くまでの LERW を枝として付け加えることを繰り返すと、重みつき全域木(全域木 $t$ を $\prod_{e\in t}c_e$ に比例する確率で選んだもの)が得られる。これは Wilson のアルゴリズムで、証明は 一様全域木 の定理「Wilson のアルゴリズム」にある。その系として、重みつき全域木の中で $a$ と $b$ を結ぶ道は $a$ から $b$ への LERW と同じ分布をもつ(Pemantle、LSW04 p. 5)。prop-lerw-det の分母も全域木と結びつく。$L:=\mathrm{diag}(c_x)-(c_{xy})$ を重みつきの Laplace 行列とすると $I-P=\mathrm{diag}(c_x)^{-1}L$ なので、$B=\{r\}$ のとき $D(V\setminus\{r\})=\det L_r/\prod_{x\ne r}c_x$ である($L_r$ は $L$ から $r$ の行と列を除いたもの)。すべての $c_e=1$ なら、$\det L_r$ は Kirchhoffの行列木定理 により全域木の個数である。

例と反例

小さな値の確かめ

$3\times3$ の格子の単純ランダムウォークで、隅 $a$ から対角の隅 $b$ への LERW は $12$ 本の単純な道のどれかになる。

確かめ方を開く

各道の確率を、消去中の道を状態とする Markov 連鎖の吸収確率として有理数で厳密に解いた値は、thm-lerw-formula・prop-lerw-det の値と $12$ 本すべてで一致し、$b$ から $a$ への LERW の値も thm-lerw-reversal のとおり一致する。辺にいくつかの重みを付けた場合も同じである(計算機で確かめた)。

可逆でない連鎖では向きの対称性が成り立たない

三角形の頂点 $\mathbb Z/3$ の上で $p(i,i+1)=\frac23$、$p(i,i-1)=\frac13$ とする。この連鎖は回路網の酔歩ではない(可逆でない)。thm-lerw-formula の証明は可逆性を使わないので、公式自体はこの連鎖でも成り立つ。$0$ から $2$ への LERW は $(0,2)$ か $(0,1,2)$ で、
$$ P_0\bigl(\mathrm{LE}=(0,1,2)\bigr)=\frac47,\qquad P_0\bigl(\mathrm{LE}=(0,2)\bigr)=\frac37 $$
である。一方、$2$ から $0$ への LERW では $P_2\bigl(\mathrm{LE}=(2,1,0)\bigr)=\frac17$ である。

計算を開く

LERW の最後の一歩は歩みの最後の一歩なので、$q:=P_0(\text{歩みが }1\text{ から }2\text{ に着く})$ を求めればよい。$0$ から $1$ へ進み(確率 $\frac23$)、$1$ から $2$ へ進むか($\frac23$)$0$ に戻ってやり直す($\frac13$)ので、$q=\frac23\bigl(\frac23+\frac13q\bigr)$ から $q=\frac47$ である。$2$ からは、$1$ へ進み($\frac13$)、$1$ から $0$ へ進むか($\frac13$)$2$ に戻る($\frac23$)ので、$q'=\frac13\bigl(\frac13+\frac23q'\bigr)$ から $q'=\frac17$ である。

$(0,1,2)$ の逆は $(2,1,0)$ なので、thm-lerw-reversal の結論は成り立たない。

主張反例外れること
既約な連鎖なら LERW の向きを逆にしても同じ分布ex-lerw-nonreversible連鎖が可逆(回路網の酔歩)であること
歩みごとに $\mathrm{LE}(w)$ の逆は逆の歩みのループ消去に等しい節「行列式と向きの対称性」の $K_4$ の歩み $(a,x,a,y,x,b)$主張が分布についてのものであること
LERW は頂点の上の Markov 連鎖である頂点 $a,x,y,b$ の $K_4$ で $a$ から $b$ への LERW が $x$ にいるとき、道が $(a,y,x)$ なら次は必ず $b$ だが、$(a,x)$ なら次が $y$ になる確率は正次の一歩が現在の点だけで決まること(実際は過去の道全体による。prop-lerw-laplacian)
どの無限グラフでも歩み全体のループを消せる$\mathbb Z^2$ の単純ランダムウォーク(原点に無限回戻る)歩みが過渡的であること(prop-lerw-transient)

関連項目

参考文献

[1]
Gregory F. Lawler; Oded Schramm; Wendelin Werner, Conformal invariance of planar loop-erased random walks and uniform spanning trees, Annals of Probability 32 (2004), no. 1B, 939–995, 2004, arXiv:math/0112234v3 の頁:p. 4(LERW の定義の帰属 [Law80]、Schramm の予想)、p. 5(UST の中の道が LERW であること [Pem91])、p. 6(Kenyon の $N^{5/4}$)、Theorem 1.1(p. 7、放射型 SLE$_2$ への収束)

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