How to Get a Perfectly Random Sample from a Generic Markov Chain and Generate a Random Spanning Tree of a Directed Graph
✍ Scribed by James Gary Propp; David Bruce Wilson
- Publisher
- Elsevier Science
- Year
- 1998
- Tongue
- English
- Weight
- 793 KB
- Volume
- 27
- Category
- Article
- ISSN
- 0196-6774
No coin nor oath required. For personal study only.
✦ Synopsis
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 article 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.'' ᮊ 1998 Academic Press