Solution
ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2018/iii/paper-214/4/b/solution
Past exam of the mathematics course of the University of Cambridge 2018 iii Paper 214 4 b Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-05
Fix a root . On a recurrent graph, a simple random walk started at any vertex hits almost surely. Run Wilson's algorithm with root : 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 .
To compare the two finite approximations, fix a finite set of edges 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 for all sufficiently large on each realization.
Couple the walks in , in , and in using the same neighbor choices while they are in the interior of . 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 has entered the partial tree, later walks cannot add any edge of : they stop on their first hit of the existing tree. Thus the indicators of membership for all edges of 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.
New to topics? Read the docs here!