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.

$\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, 2020 at 6:03
  • $\begingroup$ Edited the question. $\endgroup$
    – Sid Meier
    Aug 23, 2020 at 6:38

1 Answer 1

1
$\begingroup$

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

$\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$
    – Sid Meier
    Aug 23, 2020 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, 2020 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, 2020 at 16:12

Your Answer

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

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