David Bruce Wilson
= David Bruce Wilson
{c}
<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.<Generating Random Spanning Trees More Quickly than the Cover Time by David Bruce Wilson>[Original byline, RandomTreeWithRoot and correctness argument]{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.<Generating Random Spanning Trees More Quickly than the Cover Time by David Bruce Wilson>[Algorithm and sampling theorem]{ref}