Editing Loop-erased random walk (section)

==Uniform spanning tree==
For any graph ''G'', a [[spanning tree (mathematics)|spanning tree]] of ''G'' is a [[Glossary of graph theory#Subgraphs|subgraph]] of ''G'' containing all vertices and some of the edges, which is a [[tree (graph theory)|tree]], i.e. [[Glossary of graph theory#Connectivity|connected]] and with no [[Glossary of graph theory#cycle|cycles]]. A [[spanning tree]] chosen randomly from among all possible spanning trees [[Discrete uniform distribution|with equal probability]] is called a uniform spanning tree. There are typically exponentially many spanning trees (too many to generate them all and then choose one randomly); instead, uniform spanning trees can be generated more efficiently by an algorithm called Wilson's algorithm which uses loop-erased random walks.

The algorithm proceeds according to the following steps. First, construct a single-vertex tree ''T'' by choosing (arbitrarily) one vertex. Then, while the tree ''T'' constructed so far does not yet include all of the vertices of the graph, let ''v'' be an arbitrary vertex that is not in ''T'', perform a loop-erased random walk from ''v'' until reaching a vertex in ''T'', and add the resulting path to ''T''. Repeating this process until all vertices are included produces a uniformly distributed tree, regardless of the arbitrary choices of vertices at each step.

A connection in the other direction is also true. If ''v'' and ''w'' are two vertices in ''G'' then, in any spanning tree, they are connected by a unique path. Taking this path in the ''uniform'' spanning tree gives a random simple path. It turns out that the distribution of this path is identical to the distribution of the loop-erased random walk starting at ''v'' and stopped at ''w''. This fact can be used to justify the correctness of Wilson's algorithm. Another corollary is that loop-erased random walk is symmetric in its start and end points. More precisely, the distribution of the loop-erased random walk starting at ''v'' and stopped at ''w'' is identical to the distribution of the reversal of loop-erased random walk starting at ''w'' and stopped at ''v''. Loop-erasing a random walk and the reverse walk do not, in general, give the same result, but according to this result the distributions of the two loop-erased walks are identical.