# Probability Distributions and Computational Complexity

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.

• 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}$. Jun 7, 2014 at 17:19
• 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. Jun 8, 2014 at 18:16
• @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? Jun 8, 2014 at 21:49
• @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. Jun 9, 2014 at 10:37
• @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. Jun 12, 2014 at 17:18

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.

• 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. Jan 6, 2016 at 13:53
• @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. :) Jan 6, 2016 at 14:01
• Yes, and the main problem is that such languages (= generic, programmable samplers) are slow. How can we speed them up? Jan 6, 2016 at 14:19