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.