Arora and Barak (in chapter 18, on average-case complexity) define a polynomial-time samplable (or P-samplable) distribution $D$ (actually a family $\{D_n\}$, for each output length $n$) as having an associated probabilistic polynomial-time algorithm $S$ such that $S(1^n)$ (the output of $S$ on the string consisting of $n$ 1's) is distributed identically to $D_n$.

The authors do not explicitly define probabilistic polynomial-time algorithms in this context. However, if we use the definition of probabilistic Turing machines given in chapter 7 (definition 7.2), where every random decision is made with probability $\frac{1}{2}$, we seemingly get the unwelcome consequence that a uniform distribution over 3 elements is not P-samplable, because $\frac{1}{3}$ is not expressible as a binary fraction, i.e. $c/2^i$ for integers $c, i$.

The natural intuition from real-world programming is that we can adequately approximate non-binary-fractional probabilities $p$ (as long as the $i$th bit of $p$ is computable in time polynomial in $i$) using only a fair source of random bits. In terms of definitions that reflect this, Yamakami (1999) allows an inverse exponential error term for the probability of each outcome, but the definition appears to introduce additional complications. Is this the standard way to amend the definition? Does it preserve all the expected results?

  • 1
    $\begingroup$ If you allow your algorithm to fail (by not returning anything, or returning a special symbol) with some small probability or if you allow the running time of your algorithm to be randomized as well (say, it runs in polynomial time in expectation or with high probability), then you can also do rejection sampling. $\endgroup$
    – Tassle
    Dec 14, 2023 at 23:58


Your Answer

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