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, privacy policy and cookie policy

Browse other questions tagged or ask your own question.