Back to Search
Start Over
Lazy brute-force sampling: A universal perfect sampling scheme from Markov chains
- Publication Year :
- 2024
-
Abstract
- 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)$.<br />Comment: 12 pages
- Subjects :
- Computer Science - Computational Complexity
Mathematics - Probability
Subjects
Details
- Database :
- arXiv
- Publication Type :
- Report
- Accession number :
- edsarx.2410.00882
- Document Type :
- Working Paper