A loop-erased random walk is the self-avoiding path obtained by chronologically erasing loops from a random-walk path.
The time reversal of a Brownian motion conditioned to exit at a boundary point can be coupled to radial so that its loop-erasure is the radial curve. The coupling requires the Brownian path's first hit of each initial radial segment to occur at its tip. It is an existence theorem for a coupling and does not assert that the Brownian trace equals the simple radial curve, or that an elementary deterministic finite-loop algorithm is defined for all continuum paths.
On a finite connected unweighted graph, the graph path between and in a uniform spanning tree has the law of loop-erased random walk from to . Root Wilson's algorithm at and process first: the first attached graph path is exactly that loop erasure, and later attachments cannot change it. Changing the root to proves reversibility of loop-erased random walk, even though chronological loop erasure does not commute with reversing each individual random-walk trajectory.
Chronological loop erasure removes each loop from a finite or transient infinite path as soon as the loop is formed, producing a self-avoiding path.
On a finite undirected graph, the reversal of a loop-erased random walk from to has the law of a loop-erased random walk from to . The uniform-spanning-tree path representation proves the identity.
Articles by others on the same topic
Loop-erased random walk (LERW) is a mathematical construct and a type of random walk that is particularly interesting in the fields of probability theory and statistical mechanics. It can be thought of as a model for exploring the behavior of paths in a random environment while avoiding certain obstacles (loops). Here's how it works: 1. **Random Walk**: Begin with a simple random walk on a lattice (for example, the integer grid in two dimensions), starting from an origin point.