How to Learn Wilson’s Algorithm: Loop-Erased Random Walks, Uniform Spanning Trees, Cycle Erasure and Exact Graph Sampling

Wait, What?

A random walk can wander in circles for a long time—and those wasted loops are exactly what Wilson’s algorithm learns to throw away.

Wilson’s algorithm is one of the cleanest examples of a randomized algorithm whose output is not merely “random-looking” but exactly distributed according to a mathematical target. Given a finite connected graph, it produces a uniform spanning tree: every spanning tree is sampled with equal probability in the unweighted case. Its engine is the loop-erased random walk (LERW). A walk is allowed to wander freely, but whenever it creates a loop, that loop is removed from the retained path. Repeating this process from new starting vertices until every vertex joins the growing tree gives an exact sampler.

Quick Answer

Learn Wilson’s algorithm through spanning-tree foundations → random walks → loop erasure → growing-tree invariant → correctness intuition → uniformity → runtime → weighted variants → reproducibility → professional sampling diagnostics. The most important conceptual distinction is that Wilson’s algorithm samples from the set of spanning trees; it does not seek the minimum-cost spanning tree.

1. First Separate Three Different Problems

• Find any spanning tree: DFS or BFS can do this.
• Find a minimum spanning tree: use algorithms such as Kruskal or Prim when edges have costs.
• Sample a uniform spanning tree: choose one tree randomly so that every possible spanning tree has the same probability.

Wilson’s algorithm owns the third job. Confusing these objectives leads to incorrect benchmarks and incorrect claims. A minimum spanning tree is an optimization object. A uniform spanning tree is a probability distribution over combinatorial objects.

2. Rebuild the Spanning-Tree Idea

A spanning tree of a connected undirected graph contains every vertex, contains no cycle, and uses exactly |V|−1 edges. A small graph may have many different spanning trees. For a triangle, there are three: remove any one of the three edges. A correct uniform sampler must return each of those three with probability 1/3.

That triangle is a useful first test because you can enumerate the complete answer space. For larger graphs, enumeration becomes impossible very quickly, which is why a sampling algorithm is needed.

3. Understand the Random Walk Before Erasing It

A simple random walk at vertex v chooses one of v’s neighbours according to the specified transition probabilities and moves there. In an unweighted graph, that usually means choosing uniformly among neighbours. A random walk can revisit vertices and traverse the same edge many times.

The walk is not itself a tree. Its value is that it explores the graph according to a well-defined stochastic process. Wilson’s insight is to transform this noisy path into a simple path without destroying the distribution needed for exact tree sampling.

4. Loop Erasure Is a State-Compression Operation

Suppose a walk visits:

A → B → C → D → B → E → F

When the walk returns to B, the segment B → C → D → B forms a loop. Chronological loop erasure removes that loop, leaving:

A → B → E → F

The retained path is always simple: no vertex appears twice. A robust implementation can maintain the current path plus a map from vertex to its position in that path. When a vertex repeats, truncate the path back to the earlier occurrence.

5. The Full Wilson Procedure

choose a root r
T = {r}

while T does not contain every vertex:
    choose a start vertex s not in T
    run a random walk from s until it hits T
    erase loops chronologically from that walk
    add every retained path edge to T

return T

The tree grows monotonically. Every new loop-erased path terminates at the existing tree and introduces no cycle, because the retained path is simple and only first meets the old tree at its endpoint.

6. Trace a Five-Vertex Example

Draw a square A–B–C–D–A with a centre vertex E connected to all four corners. Pick A as root. Start from C and imagine the random walk C → E → B → C → D → A. The return to C creates a loop C → E → B → C, so chronological erasure removes it. The retained path becomes C → D → A and is added to the tree. Now perhaps start from E. Its walk stops as soon as it first reaches C, D or A, because those vertices are already in the tree.

Run this trace with dice or a pseudorandom generator before coding it. Predict where loops will be erased, then compare the prediction with the actual path.

7. Why the Result Is Uniform

David B. Wilson proved in 1996 that the algorithm produces the correct spanning-tree distribution independently of the order in which starting vertices are chosen. The deep proof can be expressed through cycle-popping and random-walk arguments, but the learner should first secure three local invariants:

• the retained path from each walk is simple;
• adding it cannot create a cycle with the existing tree;
• the process eventually spans the connected graph with probability 1.

Those invariants prove that the output is a spanning tree. Uniformity is the stronger probabilistic statement: not just “a tree,” but the correct probability for each tree. That step requires the full distribution argument, not only structural correctness.

8. Root and Start Order Affect Work, Not the Target Distribution

In the standard unweighted connected setting, changing the root or the sequence of start vertices can change how long the random walks take, but not the final uniform distribution. This creates an important engineering opportunity: choose roots strategically when performance matters, while keeping the sampling law intact under the conditions of the theorem.

9. Weighted Wilson Sampling

Wilson-style sampling extends naturally to weighted graphs by changing transition probabilities. In weighted implementations such as the Boost Graph Library, the probability of a particular spanning tree can be proportional to the product of its edge weights. That is no longer “uniform over trees,” so the probability model must be stated explicitly.

The professional lesson is that a small change in the random-walk transition rule changes the distribution being sampled. Never call a weighted sampler “uniform” unless the weighting reduces to the uniform case.

10. Runtime Is About Hitting Time, Not Just |V| and |E|

Wilson’s algorithm was introduced as a method that can generate random spanning trees more quickly than waiting for a random walk to cover the whole graph. Its work depends strongly on the graph’s random-walk geometry: how quickly a walk from a new vertex reaches the tree already built. Dense, well-connected graphs can behave very differently from long paths, lollipop-like graphs or graphs with bottlenecks.

Therefore professional benchmarking should record random-walk steps, erased-loop volume, tree-growth rate and elapsed time—not just vertex count.

11. Implementation Details That Matter

• Connectivity: verify that every relevant vertex can reach the root under the transition model. Boost warns that otherwise the walk can become stuck or loop indefinitely.
• Random generator: pass an explicit seeded generator for reproducible experiments.
• Loop erasure: use a position map rather than repeatedly scanning the entire retained path.
• Self-loops and multiedges: define how the graph representation handles them.
• Directed graphs: do not silently apply undirected uniform-tree claims to a directed setting.
• Weights: normalize valid nonnegative transition weights and document the resulting target law.

12. How to Test a Randomized Exact Sampler

Randomized algorithms need two classes of tests. First, deterministic structural tests: every output must contain all vertices, have |V|−1 edges, be connected and contain no cycle. Second, distribution tests on tiny graphs where the exact probabilities are known. For a triangle, sample perhaps tens of thousands of trees and check that the three outcomes appear near 1/3 each. Statistical variation is expected, so use confidence intervals or a goodness-of-fit test rather than demanding exact counts.

13. Professional Applications and Boundaries

Uniform spanning trees appear in probabilistic graph theory, random planar structures, electrical-network connections, sampling-based graph algorithms and applications where unbiased tree structure matters. They also provide a powerful teaching bridge between random walks, Markov chains, graph connectivity and exact combinatorial sampling.

Wilson’s algorithm should not be used as a substitute for minimum spanning trees, shortest paths, network reliability optimization or arbitrary random-tree generators. Each of those has a different target contract.

14. A Learning Sequence That Builds Transfer

• Predict: given a walk with repeated vertices, predict the loop-erased path.
• Run: execute a reference Wilson implementation on a triangle and square.
• Investigate: log every random-walk step and every erased loop.
• Modify: change root selection and start order while checking that empirical tree frequencies remain consistent.
• Make: build a sampler with seeded randomness, structural validation and distribution diagnostics.

This Predict–Run–Investigate–Modify–Make progression is consistent with PRIMM research in programming education. For learners who struggle with writing the complete routine, Parsons-style reconstruction can reduce syntax burden while preserving attention on algorithm order. Subgoal labels such as “walk until tree,” “erase loop,” and “commit path” make the invariant visible.

Common Failure States

• Confusing a random spanning tree with a minimum spanning tree.
• Erasing only the first loop instead of maintaining chronological loop erasure throughout the walk.
• Continuing the walk after it first hits the existing tree.
• Adding the raw random-walk path rather than the loop-erased path.
• Using a disconnected graph and waiting forever.
• Changing transition probabilities without realizing that the target tree distribution changes.
• Testing only whether outputs are trees and never testing the probability distribution.

Practice Ladder

• Beginner: loop-erase five hand-written walks.
• Foundation: enumerate all spanning trees of a triangle and square-with-diagonal.
• Intermediate: implement Wilson’s algorithm for small undirected graphs.
• Advanced: compare Wilson and Aldous–Broder empirically on graphs with different hitting-time structures.
• Professional: add weighted transitions, reproducible RNG streams, statistical validation, profiling and failure handling for unreachable roots.

Evidence Boundary

The canonical source is David B. Wilson, “Generating random spanning trees more quickly than the cover time,” STOC 1996, pp. 296–303, DOI 10.1145/237814.237880. Modern Boost Graph Library documentation explicitly describes its random spanning tree routine as Wilson’s loop-erased-random-walk method and documents weighted and unweighted variants. Current research on uniform spanning trees continues to use Wilson’s algorithm as a standard exact sampler.

Professional rule: you understand Wilson’s algorithm when you can distinguish structural correctness from distributional correctness, explain why loop erasure preserves a simple attachment path, and validate the sampler statistically on graphs whose spanning trees can be enumerated.