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

Aldous, 1995, On simulating a Markov chain stationary distribution when transition probabilities are unknown, 72

Aldous, 1990, A random walk construction of uniform spanning trees and uniform labelled trees, SIAM J. Discrete Math., 3, 450, 10.1137/0403039

D. J. Aldous, J. A. Fill, Reversible Markov Chains and Random Walks on Graphs, http://www.stat.berkeley.edu/~aldous/book.html

Aleliunas, 1979, Random walks, universal traversal sequences, and the complexity of maze problems

Altschul, 1985, Significance of nucleotide sequence alignments: A method for random sequence permutation that preserves dinucleotide and codon usage, Mol. Biol. Evol., 2, 526

Asmussen, 1992, Stationary detection in the initial transient problem, ACM Trans. Model. Comput. Simulation, 2, 130, 10.1145/137926.137932

Baxter, 1982

Beckett, 1994, Spectral analysis for discrete longitudinal data, Adv. in Math., 103, 107, 10.1006/aima.1994.1002

Binney, 1992

Bollobás, 1979, 63

Borovkov, 1992, Stochastically recursive sequences and their generalizations, Siberian Adv. Math., 2, 16

Broder, 1989, Generating random spanning trees, Thirtieth Annual Symposium on Foundations of Computer Science, 442, 10.1109/SFCS.1989.63516

Burton, 1993, Local characteristics, entropy and limit theorems for spanning trees and domino tilings via transfer-impedances, Ann. Probab., 21, 1329, 10.1214/aop/1176989121

Colbourn, 1987

Colbourn, 1989, Unranking and ranking spanning trees of a graph, J. Algorithms, 10, 271, 10.1016/0196-6774(89)90016-3

Colbourn, 1988, Estimating the coefficients of the reliability polynomial, Congr. Numer., 62, 217

Colbourn, 1996, Two algorithms for unranking arborescences, J. Algorithms, 20, 268, 10.1006/jagm.1996.0014

Coppersmith, 1990, Matrix multiplication via arithmetic progressions, J. Symbolic Comput., 9, 251, 10.1016/S0747-7171(08)80013-2

Diaconis, 1988

Diaconis, 1995, What do we know about the Metropolis algorithm?

Diaconis, 1991, Geometric bounds for eigenvalues of Markov chains, Ann. Appl. Probab., 1, 36, 10.1214/aoap/1177005980

Dyer, 1994, Random walks, totally unimodular matrices, and a randomised dual simplex algorithm, Math. Programming, 64, 1, 10.1007/BF01582563

Eriksson, 1996, Strong convergence and the polygon property of 1-player games, Discrete Math., 153, 105, 10.1016/0012-365X(95)00131-F

Feder, 1992, Balanced matroids

Felsner, 1997, Markov chains for linear extensions, the two-dimensional case

de la Vega, 1977, Construction de mots circulaires aléatoires uniformément distribués, Math. Sci. Humaines, 58, 25

J. A. Fill, 1995

Fill, 1997, An interruptible algorithm for perfect sampling via Markov chains

Fitch, 1983, Random sequences, J. Mol. Biol., 163, 171, 10.1016/0022-2836(83)90002-5

Fortuin, 1972, On the random cluster model. I. Introduction and relation to other models, Physica, 57, 536, 10.1016/0031-8914(72)90045-6

Glynn, 1990, Bias properties of budget constrained simulations, Oper. Res., 38, 801, 10.1287/opre.38.5.801

Griffeath, 1979, 724

Guénoche, 1983, Random spanning tree, J. Algorithms, 4, 214, 10.1016/0196-6774(83)90022-6

O. Häggström, M. N. M. van Lieshout, J. Møller, Characterisation results and Markov chain Monte Carlo algorithms including exact simulation for some spatial point processes, R-96-2040, Aalborg University, 1996

O. Häggström, K. Nelander, Exact sampling from anti-monotone systems, 1997

Holley, 1975, Ergodic theorems for weakly interacting systems and the voter model, Ann. Probab., 3, 643, 10.1214/aop/1176996306

Jerrum, 1989, Approximating the permanent, SIAM J. Comput., 18, 1149, 10.1137/0218077

Kandel, 1996, Shuffling biological sequences, Discrete Appl. Math., 71, 171, 10.1016/S0166-218X(97)81456-4

W. S. Kendall, J. Møller, Perfect Metropolis–Hastings simulation of locally stable spatial point processes

W. S. Kendall, Perfect simulation for the area-interaction point process, in, Proceedings of the Symposium on Probability Towards the Year 2000, C. C. HeydeL. Accardi, World Scientific Press

Kulkarni, 1990, Generating random combinatorial objects, J. Algorithms, 11, 185, 10.1016/0196-6774(90)90002-V

Lawler, 1991

Liggett, 1985

Lovász, 1992, On the randomized complexity of volume and diameter

Lovász, 1995, Exact mixing in an unknown Markov chain, Electron. J. Combin., 2, 10.37236/1209

Luby, 1995, Markov chain algorithms for planar lattice structures (extended abstract)

Luby, 1997, Approximately counting up to four (extended abstract)

R. B. Lund, D. B. Wilson, Exact sampling algorithms for storage systems and networks

R. Lyons, Y. Peres, Probability on Trees, http://php.indiana.edu/~rdlyons/prbtree/prbtree.html

J. Møller, A note on perfect simulation of conditionally specified models, 1997

D. J. Murdoch, P. J. Green, Exact sampling from a continuous state space, 1997

Nel, 1990, Combining Monte Carlo estimates and bounds for network reliability, Networks, 20, 277, 10.1002/net.3230200303

Pemantle, 1991, Choosing a spanning tree for the integer lattice uniformly, Ann. Probab., 19, 1559, 10.1214/aop/1176990223

C. A. Phillips, 1991

Propp, 1996, Exact sampling with coupled Markov chains and applications to statistical mechanics, Rand. Struct. Algorithms, 9, 223, 10.1002/(SICI)1098-2418(199608/09)9:1/2<223::AID-RSA14>3.0.CO;2-O

Sinclair, 1993

Temperley, 1974

D. B. Wilson, Annotated bibliography of perfectly random sampling with Markov chainsDIMACS Series in Discrete Mathematics and Theoretical Computer Science, Microsurveys in Discrete Probability, D. AldousJ. Propp, American Mathematical Society, 1998, http://dimacs.rutgers.edu/~dbwilson/exact