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. The Laplacian random walk Another representation of loop-erased random walk stems from solutions of the 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 . Let f be a function from G to R satisfying for all and f is discretely 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 using f at the neighbors of as weights. In other words, if are these neighbors, choose with probability Continuing this process, recalculating f at each step, with result in a random simple path from