<p>Using rejection sampling, it is trivial to construct a Las Vegas algorithm for sampling a uniformly random prime number less than a given <span class="math-container">$N$</span>. What is known about sampling algorithms that run in worst-case polynomial time and produce the <em>exact</em> 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.</p>

CC BY-SA 4.0
2020-10-15T06:05:48.003Z
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$.
Emil Jeřábek
CC BY-SA 4.0
2020-10-15T07:27:56.537Z
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.
Emil Jeřábek
CC BY-SA 4.0
2020-10-15T16:06:05.577Z
Fair enough. One has to look for an idealized model where such issues can be circumvented.
Mahdi Cheraghchi
CC BY-SA 4.0
2020-10-21T07:12:00.123Z
@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.
user21820
<randomized-algorithms><sampling>
Efficient sampling of primes
Mahdi Cheraghchi
# Efficient sampling of primes

(Asked by: username_0 on 2020-10-14)

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.

**Tags:** randomized-algorithms, sampling

> **Comments:**
> **username_1**: 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$.  
> **username_1**: 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.  
> **username_0**: Fair enough. One has to look for an idealized model where such issues can be circumvented.  
> **username_2**: @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.  

---

## 0 answers

