An interruptible algorithm for perfect sampling via Markov chains
type: Item
instance of: scholarly article
title: An interruptible algorithm for perfect sampling via Markov chains
zbMATH Open document ID: 0939.60084
author: James Allen Fill
published in: The Annals of Applied Probability
publication date: 1999-08-02T00:00:00Z
review text: For many examples from statistical physics and computer science one seeks to sample from a probability distribution on an enormously large state space, but elementary sampling is ruled out by the infeasibility of calculating an approximate normalizing constant. In case of Markov chain Monte Carlo approximate sampling approach one constructs and runs for a long time a Markov chain with long-run distribution \(\pi\). But determining how long is long enough to get a good approximation can be both analytically and empirically difficult. \textit{J. G. Propp} and \textit{D. B. Wilson} [Random Struct. Algorithms 9, No. 1/2, 223-252 (1996; Zbl 0859.60067)] gave an efficient algorithm to use the same Markov chains to produce perfect samples from \(\pi\). However, the running time of their algorithm is an unbounded random variable, the order of magnitude is usually unknown a priori and is not independent of the state sampled. The author presents a new algorithm which uses the same Markov chains to produce perfect samples from \(\pi\) and is based on the acceptance/rejection sampling and eliminates user-impatience bias. The new algorithm has running time of the same order as the Propp-Wilson one and uses only logarithmically more space.
Mathematics Subject Classification ID: 60J10
Mathematics Subject Classification ID: 68U20
Mathematics Subject Classification ID: 60G40
Mathematics Subject Classification ID: 62D05
zbMATH DE Number: 1319847
zbMATH Keywords: Markov chain Monte Carlo
zbMATH Keywords: perfect simulation
zbMATH Keywords: rejection sampling
reviewed by: László Lakatos
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.1214/aoap/1027961037
OpenAlex ID: W2066749736
cites work: Shuffling Cards and Stopping Times
cites work: Strong uniform times and finite random walks
cites work: Stationarity detection in the initial transient problem
cites work: Q3750011
cites work: Generalized Monte Carlo significance tests
cites work: Bayesian computation and stochastic systems. With comments and reply.
cites work: Stochastically recursive sequences and their generalizations
cites work: Two ergodicity criteria for stochastically recursive sequences
cites work: Q3995195
cites work: Strong stationary times via a new form of duality
cites work: Q4234057
cites work: Separation cut-offs for birth and death chains
cites work: The Move-to-Front Rule: A Case Study for two Perfect Sampling Algorithms
cites work: Stochastic monotonicity and realizable monotonicity
cites work: Q3321206
cites work: Simulating the Invariant Measures of Markov Chains Using Backward Coupling at Regeneration Times
cites work: Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of Images
cites work: Exact sampling from anti‐monotone systems
cites work: Characterization results and Markov chain Monte Carlo algorithms including exact simulation for some spatial point processes
cites work: Studying Convergence of Markov Chain Monte Carlo Algorithms Using Coupled Sample Paths
cites work: Stochastic inequalities on partially ordered spaces
cites work: Q3838656
cites work: Exact mixing in an unknown Markov chain
cites work: Exact sampling with coupled Markov chains and applications to statistical mechanics
cites work: Q5687553
cites work: Q3135094
cites work: Q3748279
cites work: The Existence of Probability Measures with Given Marginals
cites work: How to Get a Perfectly Random Sample from a Generic Markov Chain and Generate a Random Spanning Tree of a Directed Graph
DOI: 10.1214/AOAP/1027961037
Recommended article: Q4527037
Recommended article: Q4527093
Recommended article: Perfect simulation with exponential tails on the running time
Recommended article: Q4263659
Recommended article: Perfect simulation of the hard disks model by partial rejection sampling
description: scientific article; zbMATH DE number 1319847