0
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ – D.W.♦ Aug 23 '20 at 6:03
  • $\begingroup$ Edited the question. $\endgroup$ – BlackHat18 Aug 23 '20 at 6:38
1
$\begingroup$

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

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ How do you "sample" a bit? Do you just toss a coin? I can't seem to relate this with a physical process that the computer would be doing. $\endgroup$ – BlackHat18 Aug 23 '20 at 7:27
  • $\begingroup$ If you want to understand pseudo-random number generation, and don't have access to a copy of TAOCP, the PCG paper is probably your best bet. pcg-random.org/paper.html $\endgroup$ – Pseudonym Aug 23 '20 at 9:08
  • 1
    $\begingroup$ @BlackHat18, randomized algorithms are assumed to have access to the ability to generate random bits. It's not clear what the source of your confusion is and whether you are asking a theoretical or practical question. Perhaps you might find it useful to find a textbook on randomized algorithms and learn about that area? $\endgroup$ – D.W.♦ Aug 23 '20 at 16:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.