Kolmogorov complexity of a string is the length of the shortest algorithm that generates it. Here I'm focusing instead on randomly distributed strings $x$, with length $n$, with a probability distribution $P(x)$. What is the shortest algorithm, with access to a random number generator, that is able to generate a random $x$ as output, such that $x$ comes out with probability $P(x)$? At least, up to a given precision.
Maybe this notion of complexity is not much different from the complexity of calculating $P(x)$: once the algorithm is able to calculate $P(x)$, it can choose a random $x$ with probability $P(x)$ simply by Montecarlo calculation, which takes only a few more lines of code.
However, here the time bounds could come into play: imagine that the calculation of $P(x)$ takes exponential time in $n$ (e.g. probabilities arising from amplitudes of quantum wavefunctions), and we put a polynomial time bound in $n$. I think that, whatever is your $P(x)$, you can provide the algorithm with a suitable structure with $2^n$ elements, such that it generates the random $x$ in polynomial time. On the other hand, it is easy to imagine cases in which the random $x$s can be directly constructed without the need of the huge table of $2^n$ elements.
I would like to know if this notion of complexity of probability distribution has been developed and studied, possibly in connection with the time bounds. Any hint is welcome!
