Using rejection sampling, it is trivial to construct a Las Vegas algorithm for sampling a uniformly random prime number less than a given $N$. What is known about sampling algorithms that run in worst-case polynomial time and produce the exact uniform distribution on primes? More generally, when an efficient testing for a property is available, is there a method better than rejection sampling that would achieve worst case polynomial time exactly-uniform sampling? This seems like a classical problem (related to sampling vs counting) but I'm not sure where to look up.
$\begingroup$
$\endgroup$
4
-
2$\begingroup$ Worst-case polynomial? No such thing is known even remotely. There is no known polynomial-time algorithm that given $N$, computes a prime between $N$ and $2N$. $\endgroup$– Emil JeřábekCommented Oct 15, 2020 at 6:05
-
$\begingroup$ Not to mention that no randomized algorithm with any worst-case bound whatsoever on the running time can produce exactly even the uniform distribution on $3$ elements. The distribution produced by any such algorithm has all probabilities integer multiples of $2^{-t(n)}$, where $t(n)$ is the bound on running time. $\endgroup$– Emil JeřábekCommented Oct 15, 2020 at 7:27
-
$\begingroup$ Fair enough. One has to look for an idealized model where such issues can be circumvented. $\endgroup$– Mahdi CheraghchiCommented Oct 15, 2020 at 16:06
-
1$\begingroup$ @EmilJeřábek: What if you allow the random source to return a uniformly random number in the range ${1..n}$ for any input natural $n$? Then you can produce any rational probability distribution with finite support in $O(1)$ time. $\endgroup$– user21820Commented Oct 21, 2020 at 7:12
Add a comment
|