Résumé en anglais

This paper extends the Accept-Reject algorithm to allow the proposal distribution to change at each iteration. We first establish a necessary and sufficient condition for this generalized Accept-Reject algorithm to be valid, and then show how the resulting estimator can be improved by Rao-Blackwellization. An application of these results is to the perfect sampling technique of Fill (1998), An interruptible algorithm for perfect sampling via Markov chains, which is a generalized Accept-Reject algorithm.