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 &lt; 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&ouml;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.
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.