display | more...

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.

Log in or register to write something here or to contact authors.