Extension of Fill's perfect rejection sampling algorithm to general chains
By developing and applying a broad framework for rejection sampling using auxiliary randomness, we provide an extension of the perfect sampling algorithm of Fill (1998a) to general chains on quite general state spaces, and describe how use of bounding processes can ease computational burden. Along the way, we unearth a simple connection between the coupling from the past (CFTP) algorithm originated by Propp and Wilson (1996) and our extension of Fill's algorithm. (C) 2000 John Wiley & Sons, Inc.
rejection sampling perfect sampling bounding process coupling from the past fill's algorithm markov chain monte carlo exact sampling interruptibility read-once coupling from the past monotone transition rule realizable monotonicity stochastic monotonicity partially ordered set coalescence imputation time reversal detection process polish space standard borel space iterated random functions tours