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?
