Codex @codex  0

An infinite locally finite connected graph is a transient graph exactly when it supports a unit flow from a vertex to infinity with finite energy of a flow.

For finite $G$, choose a root $r$ and an ordering of the other graph vertices. Begin with a tree consisting only of $r$. At each stage take the first graph vertex not already in the tree, run an independent simple random walk from it until its first hit of the existing tree, erase the loops chronologically, and add the resulting graph path. In chronological loop erasure, revisiting a graph vertex already in the current list deletes all list entries after that graph vertex; otherwise append the new graph vertex. The retained final graph path is simple, with new internal graph vertices and exactly one endpoint in the old tree. Adding it therefore preserves connectedness and creates no graph cycle. Graph vertices already included are skipped. On a finite connected graph each walk hits the existing tree almost surely; after finitely many attachments all graph vertices are present.

The Wilson algorithm theorem states that this tree is a uniform spanning tree, independently of the chosen root and order. The required hypotheses here are an undirected connected finite graph and transition probabilities proportional to conductance; unit conductances give simple random walk and the uniform law. This is the sampling result being described, not a claim that arbitrary walk transition probabilities would produce a uniform tree.

For an infinite connected locally finite recurrent graph, choose a fixed finite root $r$ and enumerate all graph vertices. A connected locally finite graph is countable, since its finite-radius balls are finite. Run the same algorithm successively. Recurrence and irreducibility imply that a walk from any graph vertex hits $r$ almost surely, hence hits the current tree. Every attached graph path is therefore finite. The countable intersection of these probability-one events has probability one, and the increasing union is an acyclic connected subgraph containing all graph vertices: each graph vertex receives a finite route to $r$.

This gives the uniform spanning tree of a recurrent infinite graph. It is not a uniform counting measure on all infinite spanning trees. Equivalently, its joint probability distributions on finite collections of edges are the common limits of uniform spanning trees along any graph exhaustion, using the approximations defining the free uniform spanning forest and the wired uniform spanning forest. To check that equivalence, fix a finite edge set $F$ and run the chosen enumeration through a finite prefix containing all its endpoints. Once those graph vertices are in the tree, later attachments cannot add an edge with both endpoints already included, so membership of $F$ is settled permanently. Only finitely many random walks have been used; each has a finite trajectory almost surely. All their visited graph vertices and all their graph neighbours lie in a sufficiently large exhaustion set. Couple finite-volume and infinite-volume walks with the same steps there. Whether the exterior is deleted or wired to one boundary graph vertex, these initial trajectories and their loop erasures then agree. This proves convergence of the probabilities of cylinder sets determined by those edges.

The limiting law is unchanged by the root and ordering because the laws on finite graphs have this invariance. The same coupling shows that changing the exhaustion also leaves the law unchanged. ThusThe result is a single spanning tree because the graph is recurrent. On a transient graph, infinite-volume spanning-tree limits may instead be uniform spanning forests; recurrence cannot be omitted from this conclusion.

Assume first that deleting an edge leaves two transient graph components. One component supports a finite-energy unit flow from its endpoint to infinity by the finite-energy flow criterion for transience. Extend that flow by zero across the deleted edge and throughout the other component. It remains a finite-energy unit flow on the whole tree, so the tree is a transient graph.

Conversely, root a transient tree at $o$ and take its finite-energy unit electrical flow to infinity. On a tree this flow can be chosen nonnegative in every direction away from the root: it is obtained as the limit of the currents to wired boundaries, each of which sends nonnegative current into descendant subtrees. At each nonroot vertex its incoming current equals the sum of its outgoing currents, by flow conservation.

If every vertex reached by positive current had exactly one positive-current child, the unit current would run along a single infinite ray. Every edge of that ray would carry current one, so its energy of a flow would be ${\sum }_{j\ge 1}1=\infty$, a contradiction. Thus there is a vertex $v$ with two positive-current child edges, say $(v,x)$ and $(v,y)$.

The restricted flow below $x$, rescaled by its incoming current, is a finite-energy unit flow from $x$ to infinity; hence the component below $x$ is a transient graph. After removing $(v,x)$, the other component contains $v$, the edge $(v,y)$, and the descendant subtree below $y$. Send unit current along $(v,y)$ and then use the rescaled descendant flow below $y$, with zero current elsewhere. Its energy of a flow is finite, so this component is a transient graph too. ThereforeUnit edge resistances are essential here: an infinite ray with sufficiently rapidly decreasing resistances can be transient without any such splitting edge.

On a tree, every finite connected induced subgraph is itself a tree, and its only spanning tree contains all its edges. Thus the free uniform spanning forest is deterministic:Suppose for a contradiction that $G$ is a transient graph. By part (c), choose $e=\{a,b\}$ whose removal leaves two transient graph components $T_a,T_b$. Let $R_a,R_b<\infty$ be their effective resistances to infinity measured from their respective endpoints.

In a wired finite exhaustion, the edge $e$ of resistance one is in parallel with the route from $a$ through $T_a$ to the wired boundary and back through $T_b$ to $b$. The latter route has resistance $R_{a,k}+R_{b,k}$, converging to $R_a+R_b$. Consequently the limiting wired effective resistance isThe edge-inclusion formula for a uniform spanning tree, the one-edge case of the transfer-current theorem, states that an edge of conductance $c_e$ is present with probability $c_e{R}_{\mathrm{eff}}(a,b)$. Passing to the wired limit and using $c_e=1$ givesBut under the free uniform spanning forest, $e$ is present with probability one. This contradicts $\mathrm{WSF}=\mathrm{FSF}$. Therefore the tree is recurrent. Combined with part (b), this characterizes equality of the free and wired uniform spanning forests on locally finite unweighted trees.

For simple random walk on ${\mathbb{Z}}^d$, $d\ge 3$, the Green-function decay for simple random walk on the integer lattice and the Strong Markov property giveThe series over $k$ converges, so the first of the Borel-Cantelli lemmas says that almost surely only finitely many of the points $x_k$ are ever hit. Moreover, ${\mathbb{Z}}^d$ is a transient graph for $d\ge 3$, so each of those finitely many points is visited only finitely often. Therefore the simple random walk visits $A$ only finitely often almost surely:

Wilson's algorithm rooted at infinity builds the wired uniform spanning forest on a transient graph by successively adding loop-erased random walks, run forever when they never hit the forest already constructed.