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.

  • 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$ 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$ Oct 15, 2020 at 7:27
  • $\begingroup$ Fair enough. One has to look for an idealized model where such issues can be circumvented. $\endgroup$ 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$
    – user21820
    Oct 21, 2020 at 7:12


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.