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

<ul>
<li><p>Given a number $n$, return $i$ with $0 \leq i &lt; n$ with uniform
probability, i.e. $\mathbb{P}(i = k) = \frac{1}{n}$ for all $0 \leq k
   &lt; n$.</p></li>
<li><p>Given a number $n$, return $i$ such that $i$ is a (the G&ouml;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)}$.</p></li>
</ul>

<p>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.</p>

<p>There is no reason to restrict one's attention to
uniform  or discrete distributions.</p>

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

<p>Please feel free to close or move this question if it's inappropriate for this forum. I asked
on <a href="https://cs.stackexchange.com/questions/26485/probability-distributions-and-computational-complexity">cs.stackexchange</a> but didn't get the kind of answers
I was looking for.</p>

CC BY-SA 3.0
2014-06-28T10:30:52.393Z
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).
Niel de Beaudrap
CC BY-SA 3.0
2014-06-28T12:26:50.433Z
@NieldeBeaudrap Yes, but is the reduction to the uniform distribution always the best possible way?
Martin Berger
CC BY-SA 3.0
2014-06-28T14:10:47.640Z
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".
Niel de Beaudrap
CC BY-SA 3.0
2014-06-28T19:50:37.110Z
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.
usul
CC BY-SA 3.0
2014-06-30T16:47:29.083Z
@NieldeBeaudrap You can start with access to a  uniform distribution. That's certainly a reasonable approach. But is it the only reasonable one? Why about starting from a normal distribution as basis?
Martin Berger
CC BY-SA 3.0
2014-06-30T16:48:44.723Z
@usul If you have any form of reference, that would be helpful.
Martin Berger
CC BY-SA 3.0
2014-06-30T17:28:48.633Z
Looks like the original paper on that equivalence is Jerrum-Valiant-Vazirani 1986, and found some lecture notes: https://www.cs.princeton.edu/courses/archive/fall13/cos521/lecnotes/lec20.pdf
usul
<cc.complexity-theory><reference-request><pr.probability>
Probability distributions and computational complexity
Martin Berger
# Probability distributions and computational complexity

(Asked by: username_0 on 2014-06-28)

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](https://cs.stackexchange.com/questions/26485/probability-distributions-and-computational-complexity) but didn't get the kind of answers
I was looking for.

**Tags:** cc.complexity-theory, reference-request, pr.probability

> **Comments:**
> **username_1**: 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).  
> **username_0**: @NieldeBeaudrap Yes, but is the reduction to the uniform distribution always the best possible way?  
> **username_1**: 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".  
> **username_2**: 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.  
> **username_0**: @NieldeBeaudrap You can start with access to a  uniform distribution. That's certainly a reasonable approach. But is it the only reasonable one? Why about starting from a normal distribution as basis?  
> **username_0**: @username_2 If you have any form of reference, that would be helpful.  
> **username_2**: Looks like the original paper on that equivalence is Jerrum-Valiant-Vazirani 1986, and found some lecture notes: https://www.cs.princeton.edu/courses/archive/fall13/cos521/lecnotes/lec20.pdf  

---

## 0 answers

