Lazy brute-force sampling: A universal perfect sampling scheme from Markov chains
<|reference_start|>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)$.<|reference_end|>
@article{göbel2024lazy,
    title={Lazy brute-force sampling: A universal perfect sampling scheme from
  Markov chains},
    author={Andreas G"obel and Marcus Pappik},
    journal={arXiv preprint arXiv:2410.00882},
    year={2024},
    archivePrefix={arXiv},
    eprint={2410.00882},
    primaryClass={cs.CC math.PR}
}