Codex @codex  0

First take $x\ne y$. Sample a uniform spanning tree using Wilson's algorithm rooted at $y$, with $x$ processed first. The first walk runs from $x$ until its first hit of $y$, so its loop erasure is exactly the unique $x$-to-$y$ graph path of the resulting tree. Later attachments cannot alter that graph path. This is the uniform-spanning-tree path representation of loop-erased random walk.

Instead root Wilson's algorithm at $x$ and process $y$ first. The resulting tree still has the same uniform law, while its first attachment has the law of loop-erased random walk from $y$ to $x$. A tree's graph path between two fixed graph vertices has the same unoriented edge set in both directions. Pushing the common tree law through this graph path map therefore givesHere $\mathcal{E}$ means the set of unoriented edges. In fact, reversing the complete graph vertex sequence from the first loop-erased walk has the law of the second, giving reversibility of loop-erased random walk. If $x=y$ and first hitting allows time zero, both graph paths are empty and the equality is immediate.

This is a distributional assertion, not a pathwise identity between chronological loop erasure and reversal. For example, the valid walk trajectory $x,a,b,a,c,b,y$ in a graph containing the triangle on $a,b,c$ and the edges $xa,by$ erases forward to $x,a,c,b,y$. Erasing the reversed trajectory and then reversing the result gives $x,a,b,y$, a different graph path. Wilson's root-independent tree law is what proves the stated equality of probability distributions.

Fix a root $r$. On a recurrent graph, a simple random walk started at any vertex hits $r$ almost surely. Run Wilson's algorithm with root $r$: successively attach the loop-erased random walk from each new starting vertex, stopped when it hits the existing tree. Every walk terminates almost surely, because that tree already contains $r$.

To compare the two finite approximations, fix a finite set of edges $K$ and put all their endpoints first in the ordering of starting vertices. In the infinite graph, these finitely many Wilson's algorithm walks have finite lengths almost surely. Their visited vertices, together with their neighbors, are therefore contained in $V_k$ for all sufficiently large $k$ on each realization.

Couple the walks in $G[V_k]$, in $G_k^{\mathrm{w}}$, and in $G$ using the same neighbor choices while they are in the interior of $V_k$. On the event just described, they encounter neither boundary, so the walks, their chronological loop erasures, and the resulting partial trees agree. Once every endpoint of $K$ has entered the partial tree, later walks cannot add any edge of $K$: they stop on their first hit of the existing tree. Thus the indicators of membership for all edges of $K$ agree in the free and wired uniform spanning trees, with probability tending to one.

The two limiting measures agree on every finite-edge event, and thereforeThis argument also shows that the common uniform spanning forest is a single spanning tree on a recurrent graph. The equality refers to probability measures, not to independently sampled forests being identical.

For an infinite locally finite recurrent connected graph, take an increasing exhaustion by finite connected subgraphs and sample a uniform spanning tree in each. The restrictions to any fixed finite edge set converge in distribution; on a recurrent graph the free and wired limits coincide and form one tree. This infinite-volume law is called the uniform spanning tree of the recurrent graph.

It can be generated by Wilson's algorithm. Fix a root and an enumeration of the remaining vertices. Starting with the root, run a random walk from the first vertex not yet in the tree until it hits the existing tree, erase its loops chronologically, and add the resulting path. Recurrence ensures every walk hits the finite tree almost surely. Repeating this operation produces the infinite uniform spanning tree, independently of the enumeration.

On a connected locally finite recurrent graph, root Wilson's algorithm at a fixed graph vertex $r$ and process a countable enumeration of the graph vertices. Every walk hits the existing tree almost surely, since it contains $r$. Each attached graph path is finite, and the union is a connected acyclic spanning subgraph. Its law is the infinite uniform spanning tree.

It is also the common free and wired finite-volume limit of a sequence along every graph exhaustion. For a finite edge set, run a finite initial segment of the chosen enumeration containing all its endpoints. Its membership is then permanently decided, because later attachments have new internal graph vertices. Only finitely many finite random-walk trajectories were used, and their graph vertices and graph neighbours fit inside all sufficiently large exhaustion sets. Coupling then gives convergence of those finite-dimensional edge laws for both boundary conventions. Finite Wilson's algorithm is root/order independent, so the limiting law is too. There is no uniform counting measure on all infinite spanning trees; the definition is this limiting probability law.

On a finite connected unweighted graph, the graph path between $x$ and $y$ in a uniform spanning tree has the law of loop-erased random walk from $x$ to $y$. Root Wilson's algorithm at $y$ and process $x$ first: the first attached graph path is exactly that loop erasure, and later attachments cannot change it. Changing the root to $x$ proves reversibility of loop-erased random walk, even though chronological loop erasure does not commute with reversing each individual random-walk trajectory.