Sampling from the uniform distribution Is there an efficient classical algorithm that generates samples from the uniform distribution (or a distribution that is close to the uniform distribution in total variation distance), over the set $\{0, 1\}^{n}$, for a fixed $n$?
We can easily express the uniform distribution in terms of a formula:
$Pr(X = x) = \frac{1}{N}$, for each $x \in \{0, 1\}^{n}$ and $N = 2^{n}$.
My guess is that any distribution that can be expressed in terms of an explicit formula can be efficiently sampled from, but I can't find a concrete proof.
Sure, just sample $n$ bits, concatenate them, and output the result.