Loop-gelöschter Random Walk - Loop-erased random walk

In der Mathematik ist Loop-erased Random Walk ein Modell für einen zufälligen einfachen Pfad mit wichtigen Anwendungen in der Kombinatorik und in der Physik in der Quantenfeldtheorie . Es ist eng mit dem Uniform Spanning Tree verbunden , einem Modell für einen Random Tree . Siehe auch Random Walk für eine allgemeinere Behandlung dieses Themas.

Definition

Angenommen G ist ein Graph und ein Weg der Länge n auf G . Mit anderen Worten, sind Ecken von G so, dass und durch eine Kante verbunden sind. Dann ist die Schleifenlöschung von ein neuer einfacher Pfad, der durch Löschen aller Schleifen von in chronologischer Reihenfolge erstellt wird. Formal definieren wir Indizes induktiv mit ${\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\{i:\gamma (i)=\gamma (i_{j})\}+1\,}$

wobei "max" hier bis zur Länge des Pfades bedeutet . Die Induktion hört auf, wenn für einige wir haben . Angenommen, dies geschieht bei J, dh ist das letzte Mal . Dann ist die Schleifenlöschung von , bezeichnet mit , ein einfacher Pfad der Länge J, definiert durch ${\displaystyle\gamma}$${\displaystyle i_{j}}$${\displaystyle \gamma (i_{j})=\gamma (n)}$${\displaystyle i_{J}}$${\displaystyle i_{j}}$${\displaystyle\gamma}$${\displaystyle \mathrm{LE} (\gamma)}$

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

Nun lassen G einige Graph, lassen v eine Ecke von seinem G , und wäre R eine Irrfahrt auf seine G von Start v . Sei T eine Stoppzeit für R . Dann ist der schleifengelöschte Random Walk bis zum Zeitpunkt T LE( R ([1, T ])). Mit anderen Worten, nehmen Sie R von Anfang bis T  – das ist ein (zufälliger) Pfad – löschen Sie alle Schleifen in chronologischer Reihenfolge wie oben – Sie erhalten einen zufälligen einfachen Pfad.

Die Stoppzeit T kann fest sein, dh man kann n Schritte ausführen und dann eine Schleife löschen. Es ist jedoch normalerweise natürlicher, T als Schlagzeit in einem Satz zu nehmen. Sei beispielsweise G der Graph Z ² und R ein Random Walk ausgehend vom Punkt (0,0). Sei T der Zeitpunkt, an dem R zum ersten Mal auf den Kreis mit Radius 100 trifft (wir meinen hier natürlich einen diskretisierten Kreis). LE( R ) wird als schleifengelöschter Random Walk bezeichnet, der bei (0,0) beginnt und am Kreis endet.

Einheitlicher Spannbaum

Für jeden Graphen G ist ein aufspannender Baum von G ein Teilgraph von G , der alle Ecken und einige der Kanten enthält, der ein Baum ist , dh zusammenhängend und ohne Kreise . Ein Spanning Tree zufällig aus allen möglichen Spannbäumen gewählt mit gleicher Wahrscheinlichkeit wird ein gleichmäßig Spanning Tree genannt. Es gibt typischerweise exponentiell viele aufspannende Bäume (zu viele, um sie alle zu generieren und dann zufällig einen auszuwählen); stattdessen können einheitliche Spannbäume effizienter durch einen Algorithmus namens Wilson-Algorithmus erzeugt werden, der schleifengelöschte Random Walks verwendet.

Der Algorithmus läuft gemäß den folgenden Schritten ab. Konstruieren Sie zunächst einen Baum mit einem einzigen Knoten T, indem Sie (willkürlich) einen Knoten auswählen. Dann, während der bisher konstruierte Baum T noch nicht alle Knoten des Graphen enthält, sei v ein beliebiger Knoten, der nicht in T liegt , führe einen schleifengelöschten Random Walk von v bis zum Erreichen eines Knotens in T durch , und füge den resultierenden Pfad zu T hinzu . Das Wiederholen dieses Prozesses, bis alle Scheitelpunkte enthalten sind, erzeugt einen gleichmäßig verteilten Baum, ungeachtet der willkürlichen Auswahl von Scheitelpunkten bei jedem Schritt.

Eine Verbindung in die andere Richtung gilt auch. Wenn v und w zwei Knoten in G sind, dann sind sie in jedem aufspannenden Baum durch einen eindeutigen Pfad verbunden. Wenn man diesen Pfad im gleichförmigen Spannbaum nimmt, erhält man einen zufälligen einfachen Pfad. Es stellt sich heraus, dass die Verteilung dieses Pfades identisch mit der Verteilung des schleifengelöschten Random Walks ist, der bei v beginnt und bei w endet . Diese Tatsache kann verwendet werden, um die Korrektheit des Wilson-Algorithmus zu rechtfertigen. Eine weitere Folgerung ist, dass der durch Schleifen gelöschte Random Walk in seinen Start- und Endpunkten symmetrisch ist. Genauer gesagt ist die Verteilung der schleifengelöschten Zufallswanderung, die bei v beginnt und bei w endet, identisch mit der Verteilung der Umkehrung der Schleifen-gelöschten Zufallswanderung, die bei w beginnt und bei v endet . Das Schleifenlöschen eines Random Walks und des Reverse Walk führen im Allgemeinen nicht zum gleichen Ergebnis, aber nach diesem Ergebnis sind die Verteilungen der beiden Schleifen-ausgelöschten Walks identisch.

Der Laplace-Random Walk

Eine andere Darstellung von Loop-geraded Random Walk stammt aus Lösungen der diskreten Laplace-Gleichung . Sei G wieder ein Graph und seien v und w zwei Knoten in G . Konstruieren Sie einen zufälligen Pfad von v nach w induktiv mit dem folgenden Verfahren. Angenommen, wir haben bereits definiert . Lassen Sie f eine Funktion von seinen G bis R erfüllt ${\displaystyle \gamma (1),...,\gamma (n)}$

${\displaystyle f(\gamma(i))=0}$für alle und${\displaystyle i\leq n}$${\displaystyle f(w)=1}$

f ist überall sonst diskret harmonisch

Wobei eine Funktion f in einem Graphen an einem Punkt x diskret harmonisch ist, wenn f ( x ) gleich dem Durchschnitt von f auf den Nachbarn von x ist .

Mit f definiert wählte mit f bei den Nachbarn als Gewichte. Mit anderen Worten, wenn diese Nachbarn sind, wähle mit Wahrscheinlichkeit ${\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})}}.}$

Fortsetzen dieses Prozesses, Neuberechnen von f bei jedem Schritt, mit dem Ergebnis eines zufälligen einfachen Pfads von v nach w ; die Verteilung dieses Pfades ist identisch mit der eines schleifengelöschten Random Walks von v nach w .

Eine alternative Sichtweise ist, dass die Verteilung einer schleifengelöschten Zufallswanderung, die darauf konditioniert ist , in einem Pfad β zu beginnen, identisch mit der Schleifenlöschung einer Zufallswanderung ist, die bedingt ist, β nicht zu treffen. Diese Eigenschaft wird oft als die Markov-Eigenschaft des schleifengelöschten Random Walks bezeichnet (obwohl die Beziehung zur üblichen Markov-Eigenschaft etwas vage ist).

Es ist wichtig zu beachten, dass der Beweis der Äquivalenz zwar recht einfach ist, Modelle mit sich dynamisch ändernden harmonischen Funktionen oder Maßen jedoch typischerweise äußerst schwierig zu analysieren sind. Über den p-Laplace-Walk oder die diffusionsbegrenzte Aggregation ist praktisch nichts bekannt . Ein anderes etwas verwandtes Modell ist der Harmonic Explorer .

Schließlich sei noch ein weiterer Link erwähnt: Der Satz von Kirchhoff bezieht die Anzahl der aufspannenden Bäume eines Graphen G auf die Eigenwerte des diskreten Laplace-Operators . Siehe Spannender Baum für Details.

Gitter

Sei d die Dimension, von der wir annehmen, dass sie mindestens 2 ist. Untersuchen Sie Z ^d, dh alle Punkte mit ganzzahliger . Dies ist ein unendlicher Graph mit Grad 2 d, wenn Sie jeden Punkt mit seinen nächsten Nachbarn verbinden. Von nun an betrachten wir den schleifengelöschten Random Walk auf diesem Graphen oder seinen Untergraphen. ${\displaystyle (a_{1},...,a_{d})}$${\displaystyle a_{i}}$

Hohe Abmessungen

Der am einfachsten zu analysierende Fall ist Dimension 5 und höher. In diesem Fall stellt sich heraus, dass die Kreuzungen dort nur lokal sind. Eine Rechnung zeigt, dass, wenn man einen Random Walk der Länge n unternimmt , seine Schleifenlöschung eine Länge von der gleichen Größenordnung hat, dh n . Bei entsprechender Skalierung stellt sich heraus, dass der durch Schleifen gelöschte Random Walk (in einem geeigneten Sinne) gegen die Brownsche Bewegung konvergiert, wenn n gegen Unendlich geht. Dimension 4 ist komplizierter, aber das allgemeine Bild stimmt immer noch. Es stellt sich heraus, dass die Schleifenlöschung eines Random Walks der Länge n ungefähr Scheitelpunkte hat, aber nach einer Skalierung (die den logarithmischen Faktor berücksichtigt) konvergiert die Schleifenlöschung wieder gegen die Brownsche Bewegung. ${\displaystyle n/\log ^{1/3}n}$

Zwei Dimensionen

In zwei Dimensionen führten Argumente aus der konformen Feldtheorie und Simulationsergebnissen zu einer Reihe spannender Vermutungen. Angenommen D ist ein einfach zusammenhängender Bereich in der Ebene und x ist ein Punkt in D . Nehmen Sie den Graphen G als

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

das heißt, ein Gitter der Seitenlänge , das auf D beschränkt ist . Sei v die Ecke von G , die x am nächsten liegt . Untersuchen Sie nun einen schleifengelöschten Random Walk, der bei v beginnt und beim Auftreffen auf die "Grenze" von G angehalten wird , dh die Ecken von G, die der Grenze von D entsprechen . Dann sind die Vermutungen

• Wenn ε gegen Null geht, konvergiert die Verteilung des Pfades zu einer Verteilung auf einfachen Pfaden von x zum Rand von D (natürlich anders als die Brownsche Bewegung — in 2 Dimensionen sind die Pfade der Brownschen Bewegung nicht einfach). Diese Verteilung (bezeichnet mit ) wird als Skalierungsgrenze des schleifengelöschten Random Walks bezeichnet.${\displaystyle S_{D,x}}$
• Diese Verteilungen sind konform invariant . Wenn nämlich φ eine Riemann-Abbildung zwischen D und einem zweiten Gebiet E ist, dann

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

• Die Hausdorff-Dimension dieser Pfade ist fast sicher 5/4 .

Der erste Angriff auf diese Vermutungen kam aus der Richtung der Dominosteine . Nimmt man einen aufspannenden Baum von G und fügt ihm seinen planaren dualen hinzu , erhält man eine Domino- Kachelung eines speziellen abgeleiteten Graphen (nennen Sie ihn H ). Jede Ecke von H entspricht einer Ecke, Kante oder Fläche von G , und die Kanten von H zeigen, welche Ecke auf welcher Kante und welche Kante auf welcher Fläche liegt. Es stellt sich heraus, dass die Verwendung eines gleichmäßig aufspannenden Baums von G zu einer gleichmäßig verteilten zufälligen Domino-Kachelung von H führt . Die Anzahl der Dominosteine ​​eines Graphen kann mit Hilfe der Determinante spezieller Matrizen berechnet werden, die es erlauben, ihn mit der diskreten Green-Funktion zu verbinden, die näherungsweise konform invariant ist. Diese Argumente erlaubten zu zeigen, dass bestimmte Messgrößen des schleifengelöschten Random Walks (im Grenzwert) konform invariant sind und dass die erwartete Anzahl von Scheitelpunkten in einem schleifengelöschten Random Walk, der bei einem Kreis mit Radius r gestoppt wird, in der Größenordnung von liegt . ${\displaystyle r^{5/4}}$

2002 wurden diese Vermutungen mit der Stochastischen Löwner Evolution (positiv) aufgelöst . Grob gesagt handelt es sich um eine stochastische, konform invariante gewöhnliche Differentialgleichung, die es erlaubt, die Markov-Eigenschaft des schleifengelöschten Random Walks (und vieler anderer probabilistischer Prozesse) zu erfassen.

Drei Dimensionen

Die Skalierungsgrenze existiert und ist bei Rotationen und Dehnungen invariant. Wenn die erwartete Anzahl von Knoten in der schleifengelöschten Zufallswanderung bezeichnet wird, bis der Abstand r erreicht wird , dann ${\displaystyle L(r)}$

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

wobei ε, c und C einige positive Zahlen sind (die Zahlen können im Prinzip aus den Beweisen berechnet werden, aber der Autor hat es nicht getan). Dies legt nahe, dass die Skalierungsgrenze mit ziemlicher Sicherheit eine Hausdorff-Dimension zwischen und 5/3 haben sollte . Numerische Experimente zeigen, dass es so sein sollte . ${\displaystyle 1+\varepsilon}$${\displaystyle 1,62400\pm 0,00005}$

Anmerkungen

Verweise

• Kenyon, Richard (2000a), "Die asymptotische Determinante des diskreten Laplace", Acta Mathematica , 185 (2): 239–286, arXiv : math-ph/0011042 , doi : 10.1007/BF02392811
• Kenyon, Richard (April 2000), "Conformal invariance of domino tiling", Annals of Probability , 28 (2): 759–795, arXiv : math-ph/9910002 , doi : 10.1214/aop/1019160260
• Kenyon, Richard (März 2000), "Long-range Properties of Spanning Trees" , Journal of Mathematical Physics , 41 (3): 1338–1363, doi : 10.1063/1.533190
• Kozma, Gady (2007), "The scaling limit of loop-erased random walk in three dimensions", Acta Mathematica , 199 (1): 29–152, arXiv : math.PR/0508344 , doi : 10.1007/s11511-007- 0018-8
• Lawler, Gregory F. (September 1980), "A self-avoiding random walk", Duke Mathematical Journal , 47 (3): 655–693, doi : 10.1215/S0012-7094-80-04741-9
• Lawler, Gregory F. , "Die logarithmische Korrektur für Schleife gelöschter Random Walk in vier Dimensionen", Proceedings of the Conference zu Ehren von Jean-Pierre Kahane ( Orsay , 1993). Sonderausgabe des Journal of Fourier Analysis and Applications , S. 347–362, ISBN 9780429332838
• Lawler, Gregory F. (1999), "Loop-erased random walk", in Bramson, Maury; Durrett, Richard T. (Hrsg.), Perplexing Probleme in der Wahrscheinlichkeit: Festschrift zu Ehren von Harry Kesten , Progress in Probability, 44 , Birkhäuser, Boston, MA, S. 197–217, doi : 10.1007/978-1-4612- 2168-5
• Lawler, Gregory F. ; Schramm, Oded ; Werner, Wendelin (2004), "Conformal invariance of planar loop-erased random walks and uniform spanning tree", Annals of Probability , 32 (1B): 939–995, arXiv : math.PR/0112234 , doi : 10.1214/aop/ 1079021469
• Pemantle, Robin (1991), "Choosing a Spanning Tree for the integer lattice uniformly", Annals of Probability , 19 (4): 1559–1574, doi : 10.1214/aop/1176990223
• Schramm, Oded (2000), "Scaling limits of loop-erased random walks and uniform spanning tree", Israel Journal of Mathematics , 118 : 221–288, arXiv : math.PR/9904022 , doi : 10.1007/BF02803524
• Wilson, David Bruce (1996), "Generating random spanning trees more quick than the cover time", STOC '96: Proceedings of the Twenty-eighth Annual ACM Symposium on the Theory of Computing (Philadelphia, PA, 1996) , Association for Computing Machinery, New York, S. 296–303, doi : 10.1145/237814.237880
• Wilson, David Bruce (2010), "The dimension of loop-erased random walk in three dimensions", Physical Review E , 82 (6): 062102, arXiv : 1008.1147 , doi : 10.1103/PhysRevE.82.062102