How to Get a Perfectly Random Sample from a Generic Markov Chain and Generate a Random Spanning Tree of a Directed Graph
From MaRDI portal
Publication:4216134
DOI10.1006/jagm.1997.0917zbMath0919.68092OpenAlexW2035402840MaRDI QIDQ4216134
James Propp, David Bruce Wilson
Publication date: 23 August 1999
Published in: Journal of Algorithms (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/c0f9034d6eadd0e1c930e46dec2d8cc7d0b04638
Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10)
Related Items
Indistinguishability of trees in uniform spanning forests, Double Happiness: Enhancing the Coupled Gains of L-lag Coupling via Control Variates, Two bijective proofs for the arborescent form of the Good-Lagrange formula and some applications to colored rooted trees and cacti, Determinantal probability measures, Fundamental constants in the theory of two-dimensional uniform spanning trees, Pairwise near-maximal grand coupling of Brownian motions, The eigenvalues of the empirical transition matrix of a Markov chain, A Guide to Exact Simulation, Comparison inequalities and fastest-mixing Markov chains, History dependent quantum random walks as quantum lattice gas automata, How to couple from the past using a read-once source of randomness, On combinatorial testing problems, Perfect Sampling in Infinite Spin Systems Via Strong Spatial Mixing, The number of Euler tours of random directed graphs, Computation of the steady-state probability of Markov chain evolving on a mixed state space, A combinatorial proof of Aldous–Broder theorem for general Markov chains, Polynomial time approximate or perfect samplers for discretized Dirichlet distribution, Models of random subtrees of a graph, Relational networks of conditional preferences, Bernoulli Factories for Flow-Based Polytopes, Convergence analysis of some multivariate Markov chains using stochastic monotonicity, Combinatorial bandits, Perfect sampling methods for random forests, Loop-erased walks and total positivity, Exact sampling of determinantal point processes without eigendecomposition, Shuffling biological sequences with motif constraints, Exact integration of height probabilities in the Abelian Sandpile model, Approximate and exact solutions of intertwining equations through random spanning forests, Non-coupling from the past, Unnamed Item, A combinatorial proof of a formula of Biane and Chapuy, A CLASS OF GRAPHS WHICH HAS EFFICIENT RANKING AND UNRANKING ALGORITHMS FOR SPANNING TREES AND FORESTS, Random forests and networks analysis, On the scaling limit of loop-erased random walk excursion, Learning hidden Markov models for linear Gaussian systems with applications to event-based state estimation, Expected coalescence time for a nonuniform allocation process, Doeblin trees, A reverse Aldous-Broder algorithm, Two applications of random spanning forests, A kind of dual form for coupling from the past algorithm, to sample from Markov chain steady-state probability, Fast Simulation of Large-Scale Growth Models, Approximately counting bases of bicircular matroids, An interruptible algorithm for perfect sampling via Markov chains, The Topological Fortress of Termites, Forest matrices around the Laplacian matrix, Markov chains in a Dirichlet environment and hypergeometric integrals, Watermelons on the half-plane, A Lower Bound on the Growth Exponent for Loop-Erased Random Walk in Two Dimensions, Constrained Markov order surrogates
