= David Aldous
{c}
<David Aldous> studies <probability theory> and random combinatorial structures. His random-walk construction of a <uniform spanning tree> keeps the first-entrance edge for each newly visited vertex of a finite connected graph.<The Random Walk Construction of Uniform Spanning Trees and Uniform Labelled Trees by David Aldous>[Original byline, equation 1 and Proposition 1]{ref}
Those edges necessarily form a tree, but their uniform distribution requires a separate argument. The construction permits properties of random trees—degrees, leaves and diameter—to be studied through <random walks>. Its running time is tied to the walk's <cover time>, giving a direct link between a stochastic exploration process and a combinatorial sampling algorithm.<The Random Walk Construction of Uniform Spanning Trees and Uniform Labelled Trees by David Aldous>[Introduction and Proposition 1]{ref}
Back to article page
