Like the simple random walk (RW) and the
self-avoiding walk (SAW), the loop-erased random walk (LERW) is the
name for a statistical ensemble (ensemble is a physicist's term; mathematicians say measure)
of walks on a graph. Like members of the SAW ensemble (namely, SAWs),
LERWs don't cross themselves. That is to say, no point is visited
twice in the course of the walk.
In fact, all LERWs are SAWs and vice-versa; the names only refer
meaningfully to the ensembles. Actaully, the LERW was originally
introduced as a proposed approximation of the SAW. Later, it turned out
that it was interesting for its own sake for reasons to follow. You can
read about how the SAW ensemble is generated in the SAW node. To generate the LERW ensemble we start with the RW
ensemble that contains RWs of all lengths (i.e. the union of the
ensembles of RWs of length N for all N) and then we have
its walks undergo a loop-erasure procedure. The procedure is as
follows: go along the path of the random walk, but whenever you reach
an intersection point -- a point which the RW visited more than once --
don't leave it the way the RW did the first time it visited there (you
are also visiting the point for the first time, recall). Instead, leave
it the way the RW did the last time it visited there. Then
continue following the path of the RW after its last visit to the
intersection point. Since the RW never returned to the intersection
following its last visit there, you are now guaranteed never to
return either, and the final product of the loop-erasure procedure is
guaranteed to have no self-intersections. Thus, a loop-erased random
walk is just that, a loop-erased random walk.
The remarkable property of these walks is that the ensemble of all LERWs that start at point i and end at point j
is the same as the ensemble of paths connecting the two points on
uniform spanning trees. The uniform spanning tree (UST) being itself
an ensemble of spanning trees (trees that reach every point) on the
graph. Specifically, the ensemble that weighs each such tree the same
(hence uniform). By the property of a tree (cycle-free), there is only one path that connects every two points i and j, and it turns out that taking that path for every UST generates the same ensemble as taking all LERW from i to j.
This property is due to the fact that one way to construct a UST is to
go along the path of a RW adding every step as a branch of the tree
except when adding it would complete a cycle. Consequently, the studies
of USTs and LERWs are closely related.
Of particular interest to study is the statistics associated with
the end-to-end distance of LERW on regular grids in different spatial
dimensions. It turns out that the root-mean-square
end-to-end distance of a LERW of length N as a function of N approaches a power law for large N:
R =~ c Nν
where ν depends only on the spatial dimension and not on the particular type of grid you use to tile space. ν = 4/5 for LERWs on two-dimensional grids, ν =~ 0.62 (no exact value known) for LERWs in three dimensions, and ν = 1/2 for
LERWs in four or more dimensions (actually, in 4 dimensions there is a
logarithmic correction on top of the power law), which is the same
scaling as simple random walks in any dimension. The fact that SAWs and
LERWs have different critical exponents demonstrates that they belong
to different universality classes. Like SAWs belong to the same
universality class as the critical point of the O(n) model in the
limit that n goes to zero, LERWs belong to the universality class of the critical point in the q-state Potts model in the limit that q goes to zero.