Propp-Wilson algorithm and beyond

Abstract

Propp-Wilson algorithm is a Markov chain Monte Carlo method that produces samples that are drawn exactly from the stationary distribution of a given Markov chain. The aim of this master thesis is to unify the underlying ideas of this algorithm and to embed it into a more general framework. For this purpose, we use coupling theory as the primary tool. We also introduce Letac's principle which states that if the backward process corresponding to a Markov chain converges independent of the initial position, then its limit is distributed according to the stationary distribution of the Markov chain. With Letac's principle, su cient conditions for the convergence of backward processes become very important and this convergence is usually satis ed with the choice of contractive maps. We detail this with examples and work on a case in which we have contractivity on the average.