Lazy brute-force sampling: A universal perfect sampling scheme from Markov chains

We show that, under mild assumptions, every distribution on the hypercube $\{0, 1\}^{n}$ that admits a polynomial-time Markov chain approximate sampler also has an exact sampling algorithm with expected running time in poly$(n)$.
Comment: 12 pages