 David Bruce Wilson

David Bruce Wilson developed an exact sampling algorithm for uniform spanning trees. Wilson's algorithm grows a tree by adding loop-erased random walks, each stopped on first reaching the tree already constructed.^[ref]

Erasing loops ensures that an added path creates no cycle. The more surprising assertion is distributional: the resulting tree is uniform among spanning trees, despite the sequential construction and the choice of starting vertices. The algorithm makes a global random combinatorial object accessible through local walk operations.^[ref]