The Propp-Wilson Perfect Sampling Algorithm

Abstract:*The problem of approximate sampling using Markov Chain Monte Carlo has received considerable attention in the Theoretical Computer Science and Physics communities. In this approach one typically takes a Markov Chain $M$ with a stationary distribution $\Pi$ over a set $\mathcal{S }$ and runs it for a pre-specified amount of time $T$ from a fixed starting state $s_0$. Using various techniques such as Coupling, Spectral Gap, etc., the distribution of the output of the chain after $T$ steps, say, $s_T$,  is shown to be close to the stationary distribution $\Pi$ in total variation distance . $T$ typically has a dependence on $\log(1/\eps)$ where $\eps$ is the desired upper bound on the TV distance between the distribution of $s_T$ and $\Pi$.* *However, in this talk we will be interested in producing a sample from $\mathcal{S}$ that is distributed exactly according to $\Pi$, i.e, we require $\eps=0$. Notice, that the above approximate sampling approach cannot be used directly as we would require $T$ to be $\infty$ as it depends on $\log(1/\eps)$. To overcome the above issues Propp and Wilson [1996] came up with a beautiful algorithm known as Coupling From The Past (CFTP). In this talk we will arrive at the algorithm by taking various erroneous approaches and correcting them.*