3
$\begingroup$

Some probability distributions are easier to work with than others. Consider the following two problems.

  • Given a number $n$, return $i$ with $0 \leq i < n$ with uniform probability, i.e. $\mathbb{P}(i = k) = \frac{1}{n}$ for all $0 \leq k < n$.

  • Given a number $n$, return $i$ such that $i$ is a (the Gödel number of) a valid proof of length n in Peano arithmetic. Again $i$ should be chosen with uniform probability, i.e. if the number of such proofs is $pr(n)$, then the probability to get any specific proof of length $n$ should be $\frac{1}{pr(n)}$.

It seems inutitively clear that the latter problem is harder to solve than the former, in a way that is reminiscent of computational complexity. If we had a program solving the first problem, and a program for the second, what could we say about their time and space consumption? Moreover, whatever the intrinsic complexity of the distributions, there should be a connection with conventional complexity theory, for the difficulty of the second problem is largely a consequence of the fact that the set of valid proofs in Peano arithmetic is a complicated subset of the set of all integers, and if we had an oracle for it and / or the number of such proofs, we could solve the second problem quite easily.

There is no reason to restrict one's attention to uniform or discrete distributions.

My question is this: where has the complexity of probability distribution been investigated? What is a good overview article?

Please feel free to close or move this question if it's inappropriate for this forum. I asked on cs.stackexchange but didn't get the kind of answers I was looking for.

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ If we restrict our attention to probability distributions over finite sets with rational probabilities, there is a clear connection to computing functions $f:\Sigma^\ast\to\Omega$ in the form of reductions from a distribution (ie. simulation of a distribution) to the uniform distribution over $\Sigma^n$. The choice of input alphabet will play a more important role than usual, however, as it may make the difference between exact worst-case poly-time reductions and zero-error expected poly-time reductions (a P vs ZPP sort of distinction). $\endgroup$ – Niel de Beaudrap Jun 28 '14 at 10:30
  • $\begingroup$ @NieldeBeaudrap Yes, but is the reduction to the uniform distribution always the best possible way? $\endgroup$ – Martin Berger Jun 28 '14 at 12:26
  • 1
    $\begingroup$ The best way, to accomplish what? If we're talking about efficiently samplable distributions, then there needs to be some initial source of randomness. Be it uniform over some finite set or something else, there must be a source of indeterminism in the "elementary operations". $\endgroup$ – Niel de Beaudrap Jun 28 '14 at 14:10
  • 2
    $\begingroup$ One interesting related topic is the "equivalence" of approximate counting and sampling, which I think says that we can approximate $#L$ (the number of NP witnesses that some string $x \in L$) in polytime if and only if we can approximately uniformly generate witnesses in polynomial time. Not sure of a good reference. $\endgroup$ – usul Jun 28 '14 at 19:50
  • 1
    $\begingroup$ Looks like the original paper on that equivalence is Jerrum-Valiant-Vazirani 1986, and found some lecture notes: cs.princeton.edu/courses/archive/fall13/cos521/lecnotes/… $\endgroup$ – usul Jun 30 '14 at 17:28

Your Answer

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

Browse other questions tagged or ask your own question.