How to Get a Perfectly Random Sample From a Generic Markov Chain
and Generate a Random Spanning Tree of a Directed Graph
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.