How to Get a Perfectly Random Sample From a Generic Markov Chain
and Generate a Random Spanning Tree of a Directed Graph

James Gary Propp and David Bruce Wilson

A general problem in computational probability theory is that of generating a random sample from the state space of a Markov chain in accordance with the steady-state probability law of the chain. Another problem is that of generating a random spanning tree of a graph or spanning arborescence of a directed graph in accordance with the uniform distribution, or more generally in accordance with a distribution given by weights on the edges of the graph or digraph. This paper gives algorithms for both of these problems, improving on earlier results and exploiting the duality between the two problems. Each of the new algorithms hinges on the recently-introduced technique of coupling from the past or on the linked notions of loop-erased random walk and ``cycle-popping''.

Journal of Algorithms 27:170--217, 1998.
DVI version
PostScript version

animated illustration of cycle-popping and loop-erased random walk
SODA '96 paper, also available in the ACM's Digital Library, copyright © 1996 by ACM, Inc.
STOC '96 paper, also available in the ACM's Digital Library, copyright © 1996 by ACM, Inc.