Editing Loop-erased random walk (section)

==Definition==
Assume ''G'' is some [[Graph (discrete mathematics)|graph]] and <math>\gamma</math> is some [[path (graph theory)|path]] of length ''n'' on ''G''. In other words, <math>\gamma(1),\dots,\gamma(n)</math> are vertices of ''G'' such that <math>\gamma(i)</math> and <math>\gamma(i+1)</math> are connected by an edge. Then the '''loop erasure''' of <math>\gamma</math> is a new simple path created by erasing all the loops of <math>\gamma</math> in chronological order. Formally, we define indices <math>i_j</math> [[Mathematical induction|inductively]] using

:<math>i_1 = 1\,</math>
:<math>i_{j+1}=\max\{k:\gamma(k)=\gamma(i_j)\}+1\,</math>

where "max" here means up to the length of the path <math>\gamma</math>. The induction stops when for some <math>i_j</math> we have <math>\gamma(i_j)=\gamma(n)</math>. 

In words, to find <math>i_{j+1}</math>, we hold <math>\gamma(i_j)</math> in one hand, and with the other hand, we trace back from the end: <math>\gamma(n), \gamma(n-1), ...</math>, until we either hit some <math>\gamma(k) = \gamma(i_j) </math>, in which case we set <math>i_{j+1} = k+1</math>, or we end up at <math>\gamma(i_j)</math>, in which case we set <math>i_{j+1} = i_j+1</math>.

Assume the induction stops at ''J'' i.e. <math>\gamma(i_J)=\gamma(n)</math> is the last <math>i_J</math>. Then the loop erasure of <math>\gamma</math>, denoted by <math>\mathrm{LE}(\gamma)</math> is a simple path of length ''J'' defined by

:<math>\mathrm{LE}(\gamma)(j)=\gamma(i_j).\,</math>

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''&nbsp;— that's a (random) path&nbsp;— erase all the loops in chronological order as above&nbsp;— 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 '''Z'''<sup>2</sup> 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.