Loop-erased random walk
In mathematics, loop-erased random walk is a model for a random simple path with important applications in combinatorics, physics and quantum field theory.
is a simple path of length J defined by 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 loop-erased 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 loop-erase.
However, it is usually more natural to take T to be the hitting time in some set.
LE(R) is called the loop-erased random walk starting at (0,0) and stopped at the circle.
There are typically exponentially many spanning trees (too many to generate them all and then choose one randomly); instead, uniform spanning trees can be generated more efficiently by an algorithm called Wilson's algorithm which uses loop-erased random walks.
First, construct a single-vertex tree T by choosing (arbitrarily) one vertex.
Then, while the tree T constructed so far does not yet include all of the vertices of the graph, let v be an arbitrary vertex that is not in T, perform a loop-erased random walk from v until reaching a vertex in T, and add the resulting path to T. Repeating this process until all vertices are included produces a uniformly distributed tree, regardless of the arbitrary choices of vertices at each step.
If v and w are two vertices in G then, in any spanning tree, they are connected by a unique path.
It turns out that the distribution of this path is identical to the distribution of the loop-erased random walk starting at v and stopped at w. This fact can be used to justify the correctness of Wilson's algorithm.
Another corollary is that loop-erased random walk is symmetric in its start and end points.
Another representation of loop-erased 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.
with probability Continuing this process, recalculating f at each step, will result in a random simple path from v to w; the distribution of this path is identical to that of a loop-erased random walk from v to w. [citation needed] An alternative view is that the distribution of a loop-erased random walk conditioned to start in some path β is identical to the loop-erasure of a random walk conditioned not to hit β.
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.
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.
This is an infinite graph with degree 2d when you connect each point to its nearest neighbors.
A calculation shows that if one takes a random walk of length n, its loop-erasure has length of the same order of magnitude, i.e. n. Scaling accordingly, it turns out that loop-erased random walk converges (in an appropriate sense) to Brownian motion as n goes to infinity.
It turns out that the loop-erasure of a random walk of length n has approximately
vertices, but again, after scaling (that takes into account the logarithmic factor) the loop-erased walk converges to Brownian motion.
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 that is, a grid of side length ε restricted to D. Let v be the vertex of G closest to x.
Examine now a loop-erased 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 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).
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 loop-erased random walk are (in the limit) conformally invariant, and that the expected number of vertices in a loop-erased random walk stopped at a circle of radius r is of the order of
[1] 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 loop-erased random walk (and many other probabilistic processes).
The scaling limit exists and is invariant under rotations and dilations.
