# 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}$. – Wandering Logic Jun 7 '14 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. – Nicholas Mancuso Jun 8 '14 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? – Martin Berger Jun 8 '14 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. – Martin Berger Jun 9 '14 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. – Martin Berger Jun 12 '14 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. – Martin Berger Jan 6 '16 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. :) – Kaveh Jan 6 '16 at 14:01
• Yes, and the main problem is that such languages (= generic, programmable samplers) are slow. How can we speed them up? – Martin Berger Jan 6 '16 at 14:19

Firstly there is a basic probability theorem allowing to generate a RV with an arbitrary distribution (based on a unifrom RV) here and here

The notion of algorithmic probability which is akin to what the question asks is related to Kolmogorov-Solomonov Complexity (which is not-computable) directly.

There is a thesis (circa 2002) extending Kolmogorov Complexity (KC) to probabilistic quantum computations (not exactly what the question asks). Moreover there are directions which extend KC over the reals or un-countable sets (imo this is also peripheral to the question).

Finally there is a paper (circa 2003) which studies precisely the computational complexity of probabilistic functions in relation to entropy and distributions.

As a further option, you can also post this question on tcs.se for possible latest or more relevant references.