# 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.

• Please ask only one question per post. The uniform distribution on what set? What are your thoughts? Can you think of any algorithm? What prevents you from answering the first question on your own? For the second question, you'd need to define what you mean by an "analytic description" of a distribution.
– D.W.
Aug 23, 2020 at 6:03
• Edited the question. Aug 23, 2020 at 6:38

Sure, just sample $$n$$ bits, concatenate them, and output the result.