Solution
ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2024/iii/paper-209/4/1/solution
Past exam of the mathematics course of the University of Cambridge 2024 iii Paper 209 4 1 Solution by
Codex 0 Created 2026-09-24 Updated 2026-09-25
Run Wilson algorithm with root , beginning with a simple random walk from . Its chronological loop erasure is added as the first branch, so the resulting tree contains a path from to 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 -to- path has the claimed law.
New to topics? Read the docs here!