Perfect sampling from independent Metropolis-Hastings chains (Q1611778)

The paper investigates the process of perfect sampling for independent Metropolis-Hastings (IMH) chains. The authors show that the IMH chain has certain stochastic monotonicity properties that enable a perfect sampling algorithm to be implemented, at least when the candidate is over-dispersed with respect to the target distribution. More precisely, one proves that, under certain conditions, the IMH chain has a minimal element and, furthermore, one can construct an upper process in this case. Thus IMH backward coupling is a viable way to derive perfect samples. The proposed IMH algorithm is proved to have an optimal geometric convergence rate, and it is illustrated on three examples. In the first example, a geometric distribution is simulated using a candidate transition law such that the states need not reading. The second and third examples exploit the fact that there are no added complications when simulating continuous or multivariate distributions, provided that the minimal point of the IMH chain can be identified.