Coupling From the Past with Oracle Sampling

We propose a technique used to reduce the running time of the Coupling From The Past algorithm. It is based on the use of bounding chains, and is most useful when dealing with Markov chains that are very likely to stay in a given (bounding) state during a transition. The key idea is to modify the way in which transitions are generated, so as to change state at each iteration. It is then necessary to compensate for the bias this introduces. In this paper, we present our new algorithm, along with a proof of its correctness. We then illustrate its efficiency on a classical example: the generation of random independent sets in a graph.