In mathematics, loop-erased random walk is a model for a random simple path with important applications in combinatorics, physics and quantum field theory. It is intimately connected to the uniform spanning tree, a model for a random tree. It is a case of the more general topic of random walks.
Definition Assume G is some graph and γ {\displaystyle \gamma } is some path of length n on G. In other words, γ ( 1 ) , … , γ ( n ) {\displaystyle \gamma (1),\dots ,\gamma (n)} are vertices of G such that γ ( i ) {\displaystyle \gamma (i)} and γ ( i + 1 ) {\displaystyle \gamma (i+1)} are connected by an edge. Then the loop erasure of γ {\displaystyle \gamma } is a new simple path created by erasing all the loops of γ {\displaystyle \gamma } in chronological order. Formally, we define indices i j {\displaystyle i_{j}} inductively using
i 1 = 1 {\displaystyle i_{1}=1\,}
i j + 1 = max { k : γ ( k ) = γ ( i j ) } + 1 {\displaystyle i_{j+1}=\max\{k:\gamma (k)=\gamma (i_{j})\}+1\,}
where "max" here means up to the length of the path γ {\displaystyle \gamma } . The induction stops when for some i j {\displaystyle i_{j}} we have γ ( i j ) = γ ( n ) {\displaystyle \gamma (i_{j})=\gamma (n)} . In words, to find i j + 1 {\displaystyle i_{j+1}} , we hold γ ( i j ) {\displaystyle \gamma (i_{j})} in one hand, and with the other hand, we trace back from the end: γ ( n ) , γ ( n − 1 ) , . . . {\displaystyle \gamma (n),\gamma (n-1),...} , until we either hit some γ ( k ) = γ ( i j ) {\displaystyle \gamma (k)=\gamma (i_{j})} , in which case we set i j + 1 = k + 1 {\displaystyle i_{j+1}=k+1} , or we end up at γ ( i j ) {\displaystyle \gamma (i_{j})} , in which case we set i j + 1 = i j + 1 {\displaystyle i_{j+1}=i_{j}+1} . Assume the induction stops at J i.e. γ ( i J ) = γ ( n ) {\displaystyle \gamma (i_{J})=\gamma (n)} is the last i J {\displaystyle i_{J}} . Then the loop erasure of γ {\displaystyle \gamma } , denoted by L E ( γ ) {\displaystyle \mathrm {LE} (\gamma )} is a simple path of length J defined by
L E ( γ ) ( j ) = γ ( i j ) . {\displaystyle \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 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. For example, let G be the graph Z2 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 loop-erased random walk starting at (0,0) and stopped at the circle.
… excerpt ends here. Continue reading the full article.
