In mathematics, looperased random walk is a model for a random simple path with important applications in combinatorics and, in physics, quantum field theory. It is intimately connected to the uniform spanning tree, a model for a random tree. See also random walk for more general treatment of this topic.
Contents

Definition 1

The uniform spanning tree 2

The Laplacian random walk 3

Grids 4

High dimensions 4.1

Two dimensions 4.2

Three dimensions 4.3

Notes 5

References 6
Definition
Assume G is some graph and \gamma is some path of length n on G. In other words, \gamma(1),\dots,\gamma(n) are vertices of G such that \gamma(i) and \gamma(i+1) are connected by an edge. Then the loop erasure of \gamma is a new simple path created by erasing all the loops of \gamma in chronological order. Formally, we define indices i_j inductively using

i_1 = 1\,

i_{j+1}=\max\{i:\gamma(i)=\gamma(i_j)\}+1\,
where "max" here means up to the length of the path \gamma. The induction stops when for some i_j we have \gamma(i_j)=\gamma(n). Assume this happens at J i.e. i_J is the last i_j. Then the loop erasure of \gamma, denoted by \mathrm{LE}(\gamma) is a simple path of length J defined by

\mathrm{LE}(\gamma)(j)=\gamma(i_j).\,
Now let G be some graph, let v be a vertex of G, and let R be a random walk on G starting from v. Let T be some stopping time for R. Then the looperased random walk until time T is LE(R([1,T])). In other words, take R from its beginning until T — that's a (random) path — erase all the loops in chronological order as above — you get a random simple path.
The stopping time T may be fixed, i.e. one may perform n steps and then looperase. However, it is usually more natural to take T to be the hitting time in some set. For example, let G be the graph Z^{2} and let R be a random walk starting from the point (0,0). Let T be the time when R first hits the circle of radius 100 (we mean here of course a discretized circle). LE(R) is called the looperased random walk starting at (0,0) and stopped at the circle.
The uniform spanning tree
A spanning tree chosen randomly from among all possible spanning trees with equal probability is called a uniform spanning tree. To create such a tree Wilson’s algorithm uses looperased random walks. The algorithm proceeds by initializing the tree maze with an random starting cell. New cells are then subsequently added to the maze, initiating a random walk. The random walk progresses uninterrupted until it eventually links with the prevailing maze. However, if the random walk traverses through itself, the resulting loop is erased before the random walk proceeds. The initial random walks are unexpected to link with the small existing maze. As the maze develops, the random walks tend to have a higher probability to collide with the maze and may cause the algorithm to accelerate dramatically.
For instance, Let G again be a graph. A spanning tree of G is a subgraph of G containing all vertices and some of the edges, which is a tree, i.e. connected and with no cycles. The uniform spanning tree (UST for short) is a random spanning tree chosen among all the possible spanning trees of G with equal probability.
Let now v and w be two vertices in G. Any spanning tree contains precisely one simple path between v and w. Taking this path in the uniform spanning tree gives a random simple path. It turns out that the distribution of this path is identical to the distribution of the looperased random walk starting at v and stopped at w.
An immediate corollary is that looperased random walk is symmetric in its start and end points. More precisely, the distribution of the looperased random walk starting at v and stopped at w is identical to the distribution of the reversal of looperased random walk starting at w and stopped at v. This is not a trivial fact at all! Looperasing a path and the reverse path do not give the same result. It is only the distributions that are identical.
Apriori sampling a UST seems difficult. Even a relatively modest graph (say a 100x100 grid) has far too many spanning trees to prepare a complete list. Therefore a different approach is needed. There are a number of algorithms for sampling a UST, but we will concentrate on Wilson's algorithm.
Take any two vertices and perform looperased random walk from one to the other. Now take a third vertex (not on the constructed path) and perform looperased random walk until hitting the already constructed path. This gives a tree with either two or three leaves. Choose a fourth vertex and do looperased random walk until hitting this tree. Continue until the tree spans all the vertices. It turns out that no matter which method you use to choose the starting vertices you always end up with the same distribution on the spanning trees, namely the uniform one.
The Laplacian random walk
Another representation of looperased random walk stems from solutions of the discrete Laplace equation. Let G again be a graph and let v and w be two vertices in G. Construct a random path from v to w inductively using the following procedure. Assume we have already defined \gamma(1),...,\gamma(n). Let f be a function from G to R satisfying

f(\gamma(i))=0 for all i\leq n and f(w)=1

f is discretely harmonic everywhere else
Where a function f on a graph is discretely harmonic at a point x if f(x) equals the average of f on the neighbors of x.
With f defined choose \gamma(n+1) using f at the neighbors of \gamma(n) as weights. In other words, if x_1,...,x_d are these neighbors, choose x_i with probability

\frac{f(x_i)}{\sum_{j=1}^d f(x_j)}.
Continuing this process, recalculating f at each step, with result in a random simple path from v to w; the distribution of this path is identical to that of a looperased random walk from v to w.
An alternative view is that the distribution of a looperased random walk conditioned to start in some path β is identical to the looperasure of a random walk conditioned not to hit β. This property is often referred to as the Markov property of looperased random walk (though the relation to the usual Markov property is somewhat vague).
It is important to notice that while the proof of the equivalence is quite easy, models which involve dynamically changing harmonic functions or measures are typically extremely difficult to analyze. Practically nothing is known about the pLaplacian walk or diffusionlimited aggregation. Another somewhat related model is the harmonic explorer.
Finally there is another link that should be mentioned: Kirchhoff's theorem relates the number of spanning trees of a graph G to the eigenvalues of the discrete Laplacian. See spanning tree for details.
Grids
Let d be the dimension, which we will assume to be at least 2. Examine Z^{d} i.e. all the points (a_1,...,a_d) with integer a_i. This is an infinite graph with degree 2d when you connect each point to its nearest neighbors. From now on we will consider looperased random walk on this graph or its subgraphs.
High dimensions
The easiest case to analyze is dimension 5 and above. In this case it turns out that there the intersections are only local. A calculation shows that if one takes a random walk of length n, its looperasure has length of the same order of magnitude, i.e. n. Scaling accordingly, it turns out that looperased random walk converges (in an appropriate sense) to Brownian motion as n goes to infinity. Dimension 4 is more complicated, but the general picture is still true. It turns out that the looperasure of a random walk of length n has approximately n/\log^{1/3}n vertices, but again, after scaling (that takes into account the logarithmic factor) the looperased walk converges to Brownian motion.
Two dimensions
In two dimensions, arguments from conformal field theory and simulation results led to a number of exciting conjectures. Assume D is some simply connected domain in the plane and x is a point in D. Take the graph G to be

G:=D\cap \varepsilon \mathbb{Z}^2,
that is, a grid of side length ε restricted to D. Let v be the vertex of G closest to x. Examine now a looperased random walk starting from v and stopped when hitting the "boundary" of G, i.e. the vertices of G which correspond to the boundary of D. Then the conjectures are

As ε goes to zero the distribution of the path converges to some distribution on simple paths from x to the boundary of D (different from Brownian motion, of course — in 2 dimensions paths of Brownian motion are not simple). This distribution (denote it by S_{D,x}) is called the scaling limit of looperased random walk.

These distributions are conformally invariant. Namely, if φ is a Riemann map between D and a second domain E then

\phi(S_{D,x})=S_{E,\phi(x)}.\,
The first attack at these conjectures came from the direction of domino tilings. Taking a spanning tree of G and adding to it its planar dual one gets a domino tiling of a special derived graph (call it H). Each vertex of H corresponds to a vertex, edge or face of G, and the edges of H show which vertex lies on which edge and which edge on which face. It turns out that taking a uniform spanning tree of G leads to a uniformly distributed random domino tiling of H. The number of domino tilings of a graph can be calculated using the determinant of special matrices, which allow to connect it to the discrete Green function which is approximately conformally invariant. These arguments allowed to show that certain measurables of looperased random walk are (in the limit) conformally invariant, and that the expected number of vertices in a looperased random walk stopped at a circle of radius r is of the order of r^{5/4}.
In 2002 these conjectures were resolved (positively) using Stochastic Löwner Evolution. Very roughly, it is a stochastic conformally invariant ordinary differential equation which allows to catch the Markov property of looperased random walk (and many other probabilistic processes).
Three dimensions
The scaling limit exists and is invariant under rotations and dilations.^{[1]} If L(r) denotes the expected number of vertices in the looperased random walk until it gets to a distance of r, then

cr^{1+\varepsilon}\leq L(r)\leq Cr^{5/3}\,
where ε, c and C are some positive numbers ^{[2]} (the numbers can, in principle, be calculated from the proofs, but the author did not do it). This suggests that the scaling limit should have Hausdorff dimension between 1+\varepsilon and 5/3 almost surely. Numerical experiments show that it should be 1.62400\pm 0.00005.^{[3]}
Notes

^ Kozma, Gady (2007) "The scaling limit of looperased random walk in three dimensions", Acta Mathematica, 199 (1), 29–152 doi:10.1007/s1151100700188 preprint

^ Lawler, Gregory F. (1999) "Looperased random walk", in Perplexing problems in probability: Festschrift in honor of Harry Kesten (M. Bramson and R. T. Durrett, eds.), Progr. Probab., vol. 44, Birkhäuser Boston, Boston, MA, 1999, pp. 197–217.

^ Wilson, David B. (2010) "The dimension of looperased random walk in 3D", Physical Review E,82(6):062102.
References

Richard Kenyon, The asymptotic determinant of the discrete Laplacian, Acta Math. 185:2 (2000), 239286, online version.

Richard Kenyon, Conformal invariance of domino tiling, Ann. Probab. 28:2 (2000), 759795, online version.

Richard Kenyon, Longrange properties of spanning trees, Probabilistic techniques in equilibrium and nonequilibrium statistical physics, J. Math. Phys. 41:3 (2000), 13381363, online version.

Gady Kozma, The scaling limit of looperased random walk in three dimensions, Acta Math. 199:1 (2007), 29152, online version.

Gregory F. Lawler, A self avoiding walk, Duke Math. J. 47 (1980), 655694. The original definition and a proof of the Markov property.

Gregory F. Lawler, The logarithmic correction for looperased random walk in four dimensions, Proceedings of the Conference in Honor of JeanPierre kahane (Orsay, 1993). Special issue of J. Fourier Anal. Appl., 347362.

Gregory F. Lawler, Oded Schramm, Wendelin Werner, Conformal invariance of planar looperased random walks and uniform spanning trees, Ann. Probab. 32:1B (2004), 939995, online version.

Robin Pemantle, Choosing a spanning tree for the integer lattice uniformly, Ann. Probab. 19:4 (1991), 15591574.

Oded Schramm, Scaling limits of looperased random walks and uniform spanning trees, Israel J. Math. 118 (2000), 221288.

David Bruce Wilson, Generating random spanning trees more quickly than the cover time, Proceedings of the Twentyeighth Annual ACM Symposium on the Theory of Computing (Philadelphia, PA, 1996), 296303, ACM, New York, 1996.
This article was sourced from Creative Commons AttributionShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, EGovernment Act of 2002.
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a nonprofit organization.