Loop-erased Random Walk - The Uniform Spanning Tree

The Uniform Spanning Tree

Let G again be a graph. A spanning tree of G is a subgraph of G containing all vertices and some of the edges, which is a tree, i.e. connected and with no cycles. The uniform spanning tree (UST for short) is a random spanning tree chosen among all the possible spanning trees of G with equal probability.

Let now v and w be two vertices in G. Any spanning tree contains precisely one simple path between v and w. 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.

An immediate 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. This is not a trivial fact at all! Loop-erasing a path and the reverse path do not give the same result. It is only the distributions that are identical.

A-priori sampling a UST seems difficult. Even a relatively modest graph (say a 100x100 grid) has way too many spanning trees to prepare a complete list. Therefore a different approach is needed. There are a number of algorithms for sampling a UST, but we will concentrate on Wilson's algorithm.

Take any two vertices and perform loop-erased random walk from one to the other. Now take a third vertex (not on the constructed path) and perform loop-erased random walk until hitting the already constructed path. This gives a tree with either two or three leaves. Choose a fourth vertex and do loop-erased random walk until hitting this tree. Continue until the tree spans all the vertices. It turns out that no matter which method you use to choose the starting vertices you always end up with the same distribution on the spanning trees, namely the uniform one.