Premium
Extension of Fill's perfect rejection sampling algorithm to general chains
Author(s) -
Fill James Allen,
Machida Motoya,
Murdoch Duncan J.,
Rosenthal Jeffrey S.
Publication year - 2000
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/1098-2418(200010/12)17:3/4<290::aid-rsa6>3.0.co;2-q
Subject(s) - extension (predicate logic) , randomness , bounding overwatch , algorithm , sampling (signal processing) , computer science , simple (philosophy) , connection (principal bundle) , rejection sampling , mathematics , theoretical computer science , artificial intelligence , statistics , programming language , hybrid monte carlo , markov chain monte carlo , philosophy , geometry , filter (signal processing) , epistemology , computer vision , bayesian probability
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. © 2000 John Wiley & Sons, Inc. Random Struct. Alg., 17: 290–316, 2000