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

数学において、ループ消去ランダムウォークは、組合せ論、物理学、量子場の理論で重要な応用を持つランダム な単純パスのモデルです。これは、ランダムツリーのモデルである一様全域木と密接に関係しています。このトピックのより一般的な扱いについては、 ランダムウォークも参照してください。

Gが何らかのグラフであり、 がG上の長さnの何らかのパスであると仮定します。言い換えると、はGの頂点であり、と は辺で接続されています。この場合、のループ消去は、のループを時系列順にすべて消去することで作成される新しい単純なパスです。正式には、インデックスを次のように帰納的に定義します 。${\displaystyle \gamma }$${\displaystyle \gamma (1),\dots ,\gamma (n)}$${\displaystyle \gamma (i)}$${\displaystyle \gamma (i+1)}$${\displaystyle \gamma }$${\displaystyle \gamma }$${\displaystyle i_{j}}$

${\displaystyle i_{1}=1\,}$

${\displaystyle i_{j+1}=\max\{k:\gamma (k)=\gamma (i_{j})\}+1\,}$

ここでの「最大」は経路の長さまでを意味します。ある に対してが成立すると、この帰納法は終了します。 ${\displaystyle \gamma }$${\displaystyle i_{j}}$${\displaystyle \gamma (i_{j})=\gamma (n)}$

つまり、 を見つけるには、一方の手で を持ち、もう一方の手で の端からをたどり、 に達するまで、つまり に達する場合は を設定するか、 に達する場合は を設定するまで、たどります。 ${\displaystyle i_{j+1}}$${\displaystyle \gamma (i_{j})}$${\displaystyle \gamma (n),\gamma (n-1),...}$${\displaystyle \gamma (k)=\gamma (i_{j})}$${\displaystyle i_{j+1}=k+1}$${\displaystyle \gamma (i_{j})}$${\displaystyle i_{j+1}=i_{j}+1}$

帰納法がJで停止すると仮定します。つまり、 は最後の です。すると、 のループ消去は、 で表され、長さJで定義される 単純なパスになります。${\displaystyle \gamma (i_{J})=\gamma (n)}$${\displaystyle i_{J}}$${\displaystyle \gamma }$${\displaystyle \mathrm {LE} (\gamma )}$

${\displaystyle \mathrm {LE} (\gamma )(j)=\gamma (i_{j}).\,}$

ここで、G を何らかのグラフ、v をGの頂点、R をvから始まるG上のランダムウォークとします。T をRの停止時間とします。すると、時刻Tまでのループ消去されたランダムウォークはLE( R ([1, T ])) です。つまり、R を最初からTまで取ります 。これは (ランダムな) パスです。上記のように、すべてのループを時系列順に消去すると、ランダムな単純なパスが得られます。

停止時間T は固定されている場合があります。つまり、nステップを実行してからループ消去することができます。ただし、通常は、 T を何らかのセットのヒット時間と見なす方が自然です。たとえば、G をグラフZ ²とし、R を点 (0,0) から始まるランダム ウォークとします。T を、R が半径 100 の円 (ここでは、もちろん離散化された円を意味します) に最初にヒットする時間とします。LE ( R ) は、(0,0) から始まり、円で停止するループ消去ランダム ウォークと呼ばれます。

任意のグラフGについて、Gの全域木は、すべての頂点といくつかの辺を含むGのサブグラフであり、木、つまり連結されており閉路がないものです。すべての可能な全域木の中から等確率でランダムに選択された全域木は、一様全域木と呼ばれます。通常、全域木の数は指数的に多くなります (すべてを生成してからランダムに 1 つを選択するには数が多すぎます)。代わりに、一様全域木は、ループ消去ランダム ウォークを使用するウィルソンのアルゴリズムと呼ばれるアルゴリズムによって、より効率的に生成できます。

アルゴリズムは、次の手順で進行します。まず、（任意に）1 つの頂点を選択して、単一頂点ツリーTを構築します。次に、これまでに構築されたツリーTにはまだグラフのすべての頂点が含まれていないため、v をTに含まれない任意の頂点とし、 vからT内の頂点に到達するまでループ消去ランダム ウォークを実行し、結果のパスをTに追加します。すべての頂点が含まれるまでこのプロセスを繰り返すと、各ステップでの任意の頂点の選択に関係なく、均一に分散されたツリーが生成されます。

逆方向の接続も真です。vとw がGの 2 つの頂点である場合、任意の全域木において、それらは一意のパスによって接続されます。一様全域木でこのパスをとると、ランダムな単純パスが得られます。このパスの分布は、 vで始まりwで停止するループ消去ランダム ウォークの分布と同一であることがわかります。この事実は、ウィルソンのアルゴリズムの正しさを正当化するために使用できます。もう 1 つの帰結は、ループ消去ランダム ウォークは開始点と終了点で対称であるということです。より正確には、vで始まりwで停止するループ消去ランダム ウォークの分布は、 wで始まりvで停止するループ消去ランダム ウォークの逆の分布と同一です。ループ消去ランダム ウォークと逆のウォークは、一般に同じ結果にはなりませんが、この結果によれば、 2 つのループ消去ウォークの分布は同一です。

ループ消去ランダムウォークの別の表現は、離散 ラプラス方程式の解から生じます。Gを再びグラフとし、vとw をGの2つの頂点とします。次の手順を使用して、 vからwへのランダムパスを帰納的に構築します。 をすでに定義していると仮定します。fをGからRへの関数とし、次式を満たします 。${\displaystyle \gamma (1),...,\gamma (n)}$

${\displaystyle f(\gamma (i))=0}$すべての人のために${\displaystyle i\leq n}$${\displaystyle f(w)=1}$

fは他の場所では離散的に調和的である

グラフ上の関数f が点xにおいて離散的に調和であるとは、 f ( x ) がxの近傍におけるfの平均に等しい場合をいいます。

fが定義されている場合、重みとして近傍のfを使用して選択します。言い換えると、これらの近傍がの場合、確率で 選択します。${\displaystyle \gamma (n+1)}$${\displaystyle \gamma (n)}$${\displaystyle x_{1},...,x_{d}}$${\displaystyle x_{i}}$

${\displaystyle {\frac {f(x_{i})}{\sum _{j=1}^{d}f(x_{j})}}.}$

このプロセスを継続し、各ステップでfを再計算すると、 vからwへのランダムな単純なパスが生成されます。このパスの分布は、 vからwへのループ消去ランダムウォークの分布と同一です。^{[引用が必要]}

別の見方としては、何らかのパス β から開始するように条件付けられたループ消去ランダム ウォークの分布は、 β に到達しないように条件付けられたランダム ウォークのループ消去と同一であるというものがあります。この特性は、ループ消去ランダム ウォークのマルコフ特性と呼ばれることがよくあります (ただし、通常のマルコフ特性との関係はややあいまいです)。

等価性の証明は非常に簡単ですが、動的に変化する調和関数や尺度を含むモデルは、通常、分析が非常に難しいことに注意することが重要です。 p-ラプラシアンウォークや拡散制限凝集については、事実上何もわかっていません。 関連するもう 1 つのモデルは、調和エクスプローラです。

最後に、言及すべきもう 1 つのリンクがあります。キルヒホッフの定理は、グラフGの全域木の数を離散ラプラシアンの固有値に関連付けます。詳細については、 全域木を参照してください。

次元をdとします。次元は少なくとも 2 であると仮定します。Z ^d、つまり整数 のすべての点を調べます。これは、各点を最も近い隣接点に接続すると、次数 2 dの無限グラフになります。ここからは、このグラフまたはそのサブグラフ上のループ消去ランダムウォークを検討します。 ${\displaystyle (a_{1},...,a_{d})}$${\displaystyle a_{i}}$

分析が最も簡単なケースは、次元 5 以上です。この場合、交差は局所的であることがわかります。計算により、長さnのランダム ウォークをとると、そのループ消去の長さは同じ桁、つまりnになります。それに応じてスケーリングすると、ループ消去されたランダム ウォークは、 n が無限大になるにつれて(適切な意味で)ブラウン運動に収束することがわかります。次元 4 はより複雑ですが、概要は依然として当てはまります。長さnのランダム ウォークのループ消去にはおよそ頂点がありますが、この場合も、スケーリング (対数係数を考慮) 後、ループ消去されたウォークはブラウン運動に収束します。 ${\displaystyle n/\log ^{1/3}n}$

2次元では、共形場理論とシミュレーション結果からの議論から、多くの興味深い推測が導き出された。Dが平面内の単連結 領域であり、 x がD内の点であると仮定する。グラフG を次のように する。

${\displaystyle G:=D\cap \varepsilon \mathbb {Z} ^{2},}$

つまり、Dに制限された辺の長さ ε のグリッドです。v をxに最も近いGの頂点とします。次に、 vから始まり、 Gの「境界」、つまりDの境界に対応するGの頂点に当たったときに停止するループ消去ランダムウォークを調べます。すると、予想は 次のようになります。

• ε がゼロに近づくにつれて、経路の分布はxからDの境界までの単純な経路上の分布に収束します(もちろんブラウン運動とは異なります。2 次元ではブラウン運動の経路は単純ではありません)。この分布 ( と表記) は、ループ消去ランダム ウォークのスケーリング限界と呼ばれます。${\displaystyle S_{D,x}}$
• これらの分布は共形不変である。つまり、φがDと第二の領域Eの間のリーマン写像であるとき、

${\displaystyle \phi (S_{D,x})=S_{E,\phi (x)}.\,}$

• これらのパスのハウスドルフ次元はほぼ確実に5/4 です。

これらの予想に対する最初の攻撃は、ドミノタイリングの方向から来ました。 Gの全域木を取り、それにその平面双対グラフを追加すると、特別な導出グラフ ( Hと呼ぶ) のドミノタイリングが得られます。Hの各頂点は、 Gの頂点、辺、または面に対応し、 Hの辺は、どの頂点がどの辺にあり、どの辺がどの面にあるかを示します。Gの一様全域木を取ると、 Hの一様分布ランダムドミノタイリングにつながることがわかります。グラフのドミノタイリングの数は、特殊行列の行列式を使用して計算でき、これにより、ほぼ共形不変である離散グリーン関数にグラフを接続できます。これらの議論により、ループ消去ランダムウォークの特定の測定可能値は（極限では）共形不変であり、半径rの円で停止したループ消去ランダムウォークの頂点の期待数はのオーダーであることが示されました。^[1]${\displaystyle r^{5/4}}$

2002 年に、これらの推測は、確率的 Löwner Evolution を使用して (肯定的に) 解決されました。非常に大まかに言えば、これは、ループ消去ランダム ウォーク (および他の多くの確率的プロセス) のマルコフ特性を捉えることを可能にする、確率的共形不変常微分 方程式です。

スケーリング限界は存在し、回転や拡大に対して不変である。^[2]ループ消去ランダムウォークがrの距離に到達するまでの頂点の期待数を とすると、 ${\displaystyle L(r)}$

${\displaystyle cr^{1+\varepsilon }\leq L(r)\leq Cr^{5/3}\,}$

ここで、ε、c、Cは正の数である^[3]（これらの数は原理的には証明から計算できるが、著者は計算していない）。これは、スケーリング限界がほぼ確実に5/3から5の間にハウスドルフ次元を持つはずであることを示唆している。数値実験では、それが であるはずであることが示されている。^[4]${\displaystyle 1+\varepsilon }$${\displaystyle 1.62400\pm 0.00005}$

• ケニオン、リチャード(2000a)、「離散ラプラシアンの漸近行列式」、Acta Mathematica、185 (2): 239–286、arXiv : math-ph/0011042、doi : 10.1007/BF02392811
• ケニオン、リチャード（2000年4月）、「ドミノタイリングの共形不変性」、Annals of Probability、28（2）：759–795、arXiv：math-ph/9910002、doi：10.1214/aop/1019160260
• Kenyon, Richard (2000 年 3 月)、「スパニング ツリーの長距離特性」、Journal of Mathematical Physics、41 (3): 1338–1363、Bibcode :2000JMP....41.1338K、doi : 10.1063/1.533190、2004年 11 月 13 日にオリジナルからアーカイブ
• Kozma, Gady (2007)、「3次元におけるループ消去ランダムウォークのスケーリング限界」、Acta Mathematica、199 ( 1): 29–152、arXiv : math.PR/0508344、doi : 10.1007 /s11511-007-0018-8
• ローラー、グレゴリー F. (1980 年 9 月)、「自己回避ランダムウォーク」、デューク数学ジャーナル、47 (3): 655–693、doi :10.1215/S0012-7094-80-04741-9
• Lawler, Gregory F.、「4 次元におけるループ消去ランダムウォークの対数補正」、Jean-Pierre Kahane 記念会議議事録 ( Orsay、1993)。Journal of Fourier Analysis and Applications 特別号、pp. 347–362、ISBN 9780429332838
• Lawler, Gregory F. (1999)、「ループ消去ランダムウォーク」、Bramson, Maury、Durrett, Richard T. (編)、確率における複雑な問題: Harry Kesten を記念した記念論文集、Progress in Probability、vol. 44、Birkhäuser、ボストン、MA、pp. 197–217、doi :10.1007/978-1-4612-2168-5、ISBN 978-1-4612-7442-1
• Lawler, Gregory F. ; Schramm, Oded ; Werner, Wendelin (2004)、「平面ループ消去ランダムウォークと均一スパニングツリーの共形不変性」、Annals of Probability、32 (1B): 939–995、arXiv : math.PR/0112234、doi : 10.1214 / aop/1079021469
• Pemantle, Robin (1991)、「整数格子の全域木を一様に選択する」、Annals of Probability、19 (4): 1559–1574、arXiv : math/0404043、doi : 10.1214/aop/1176990223
• Schramm, Oded (2000)、「ループ消去ランダムウォークと均一スパニングツリーのスケーリング限界」、Israel Journal of Mathematics、118 : 221–288、arXiv : math.PR/9904022、doi : 10.1007/ BF02803524
• Wilson, David Bruce (1996)、「カバー時間よりも速くランダム スパニング ツリーを生成する」、STOC '96: Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing (Philadelphia, PA, 1996)、Association for Computing Machinery、ニューヨーク、pp. 296–303、doi :10.1145/237814.237880、S2CID  207198080
• ウィルソン、デイビッド・ブルース (2010)、「3 次元におけるループ消去ランダムウォークの次元」、Physical Review E、82 (6): 062102、arXiv : 1008.1147、Bibcode :2010PhRvE..82f2102W、doi :10.1103/PhysRevE.82.062102、PMID  21230692