Editing Loop-erased random walk (section)

==The Laplacian random walk==
Another representation of loop-erased random walk stems from solutions of the [[Discrete mathematics|discrete]] [[Laplace equation]]. Let ''G'' again be a graph and let ''v'' and ''w'' be two vertices in ''G''. Construct a random path from ''v'' to ''w'' inductively using the following procedure. Assume we have already defined <math>\gamma(1),...,\gamma(n)</math>. Let ''f'' be a function from ''G'' to '''R''' satisfying

:<math>f(\gamma(i))=0</math> for all <math>i\leq n</math> and <math>f(w)=1</math>
:''f'' is discretely [[Harmonic function|harmonic]] everywhere else

Where a function ''f'' on a graph is discretely harmonic at a point ''x'' if ''f''(''x'') equals the average of ''f'' on the neighbors of ''x''.

With ''f'' defined choose <math>\gamma(n+1)</math> using ''f'' at the neighbors of <math>\gamma(n)</math> as weights. In other words, if <math>x_1,...,x_d</math> are these neighbors, choose <math>x_i</math> with probability

:<math>\frac{f(x_i)}{\sum_{j=1}^d f(x_j)}.</math>

Continuing this process, recalculating ''f'' at each step, will result in a random simple path from ''v'' to ''w''; the distribution of this path is identical to that of a loop-erased random walk from ''v'' to ''w''. {{Citation needed|date=March 2024}}

An alternative view is that the distribution of a loop-erased random walk [[Conditional probability|conditioned]] to start in some path β is identical to the loop-erasure of a random walk conditioned not to hit β. This property is often referred to as the '''Markov property''' of loop-erased random walk (though the relation to the usual [[Markov property]] is somewhat vague).

It is important to notice that while the proof of the equivalence is quite easy, models which involve dynamically changing harmonic functions or measures are typically extremely difficult to analyze. Practically nothing is known about the [[p-Laplacian walk]] or [[Brownian tree|diffusion-limited aggregation]]. Another somewhat related model is the [[harmonic explorer]].

Finally there is another link that should be mentioned: [[Kirchhoff's theorem]] relates the number of spanning trees of a graph ''G'' to the [[eigenvalue]]s of the discrete [[Laplacian]]. See [[spanning tree (mathematics)|spanning tree]] for details.