10
$\begingroup$

This question is about the intersection of probability theory and computational complexity. One key observation is that some distributions are easier to generate than others. For example, the problem

Given a number $n$, return a uniformly distributed number $i$ with $0 \leq i < n$.

is easy to solve. On the other hand, the following problem is or appears to be much harder.

Given a number $n$, return a number $i$ such that $i$ is (the Gödel number of) a valid proof of length n in Peano arithmetic. Moreover, 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)}$.

This suggests to me that probability distributions come with a notion of computational complexity. Moreover, this complexity is probably closely related to the underlying decision problems (whether sub-recursive, e.g. $P$, $EXP$, recursive, recursively enumerable, or worse).

My question is: how does one define the computational complexity of probability distributions, especially where the underlying decision problem is not decidable. I'm sure this has been investigated already, but I'm not sure where to look.

Improve this question
$\endgroup$
11
  • 1
    $\begingroup$ Another interesting example (but which is decidable) is the quantum fourier transform. Given $f(k)=a^k \mod b$ return a number $l \in [0,N]$ such that the probability of $l$ is proportional to $\left|F(l)\right|$, $F(l) = \sum_{k=0}^N f(k) e^{-2\pi ikl/N}$. $\endgroup$
    – Wandering Logic
    Commented Jun 7, 2014 at 17:19
  • 1
    $\begingroup$ Both of your examples are discrete uniform distributions. I would imagine the differing complexities would be in how hard it is to count $|\chi|$ where $\chi$ is the support. $\endgroup$
    – Nicholas Mancuso
    Commented Jun 8, 2014 at 18:16
  • 1
    $\begingroup$ @NicholasMancuso I agree that counting + unform choice can always be used. So in some sense it gives an upper bound. Is this all that can be said? Where in the literature has this been investigated? $\endgroup$
    – Martin Berger
    Commented Jun 8, 2014 at 21:49
  • 1
    $\begingroup$ @NicholasMancuso The examples I give are uniform distributions. But one can ask the same question about non-uniform distributions. One can also wonder about distributions on $\mathbb{R}$. As regards discrete distributions: prima facie, counting doesn't appear to be enough in general, you also need to be able to generate the $i$-th element, after you've uniformly chosen $i$. That said, it might be the case that counting is the core of the problem. $\endgroup$
    – Martin Berger
    Commented Jun 9, 2014 at 10:37
  • 1
    $\begingroup$ @NikosM. Thanks, but that link too doesn't say anything about the complexity of the underlying distribution. The reference talks about a transformation $\phi$ on the uniform distribution. But that transformation might be hard / or easy computationally. $\endgroup$
    – Martin Berger
    Commented Jun 12, 2014 at 17:18

1 Answer 1

Reset to default
2
$\begingroup$

The complexity of probability distributions comes up particularly in the study of distributional problems like DistNP in Levin's theory of average case complexity theory.

A distribution is P-computable if its cumulative density function can be evaluated in polynomial time.

A distribution is P-samplable if we can sample from them in polynomial time.

If a distribution is P-computable then it is P-sampable. The reverse is not true if certain one-way functions exist.

You can extend the definitions to other complexity classes.

Oded Goldreich has a nice introductory notes on the topic that you may want to check.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thanks, I think a theory of $P$-samplable distributions is something like what I've been looking for. But there is no reason to restrict attention to $P$, you can define $C$-samplable distributions for any complexity class $C$. With the recent rise of probabilistic programming languages that is becoming vital. $\endgroup$
    – Martin Berger
    Commented Jan 6, 2016 at 13:53
  • $\begingroup$ @Martin, yes. There was a tutorial on Probabilistic Programming (slides, the video is going to be posted as well) at NIPS 2015. I heard people who attended found it very interesting. Nice to see people working at the intersection of ML/Stats and PL. :) $\endgroup$
    – Kaveh
    Commented Jan 6, 2016 at 14:01
  • $\begingroup$ Yes, and the main problem is that such languages (= generic, programmable samplers) are slow. How can we speed them up? $\endgroup$
    – Martin Berger
    Commented Jan 6, 2016 at 14:19

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.