Past exam of the mathematics course of the University of Cambridge / 2024 / iii / Paper 209 / 4

Run Wilson algorithm with root $a$, beginning with a simple random walk from $x_1$. Its chronological loop erasure is added as the first branch, so the resulting tree contains a path from $x_1$ to $a$ with exactly the law of the stated loop-erased random walk.

For completeness, the algorithm produces a uniform spanning tree. For any prescribed ordered collection of loop-erased branches, the random-walk decomposition gives a product of local transition factors and diagonal killed Green functions. The transition factors depend only on the resulting oriented tree, while the product of Green functions is independent of the vertex order by Question 3. Thus every spanning tree receives the same probability. Since a tree has a unique simple path between two vertices, its $x_1$-to-$a$ path has the claimed law.

Sample a uniform spanning tree $T$. Rooting Wilson's algorithm at $a$ shows that the path in $T$ oriented from $x_1$ to $a$ has the law of $\mathrm{LE}(x_1\to a)$. Rooting the same uniform law at $x_1$ shows that the same undirected path with its orientation reversed has the law of $\mathrm{LE}(a\to x_1)$. ConsequentlyThis is reversibility of loop-erased random walk.

Yes. Simple random walk in two dimensions is recurrent, so a walk started at $x_1$ hits $a$ almost surely and its loop erasure is a finite path. Exhaust ${\mathbb{Z}}^2$ by finite boxes, or use increasingly large tori with the marked vertices kept fixed. The probability that either walk reaches the boundary before hitting its target tends to zero by recurrence. The finite-graph reversal identity from part 2 therefore passes to the limit: