Has anyone studied an equivalent to algorithmic complexity for probability distributions?
This would be a measure which was similar to Kolmogorov complexity but look at the complexity of a (discreet or continuous) random distribution (of whatever set) instead. It could describe the distribution's complexity as, say, the smallest random Turing Machine which could produce that distribution (the complexity would be infinity if no such random Turing Machine existed).
(I would guess there could be issues around whether this measure would be unique and well-defined so I'm asking both if a definition like this makes sense and whether anyone has explored such a measure)
Edit: I realize that I should have said "sequence" instead of distribution. Yes, it is fairly trivial see that a distribution would have an ordinary Kolmogorov complex since it can be specified by a finite string (or not). The question would be whether a subset of the set of infinite sequences could be uniquely assigned a probability distribution that could generate them and thus be assigned a "complexity minus randomness" measure.
But when I revise the requirements like that, I think the answer would be "no" or "yes" very trivially - you can create a "universal distribution" would picks "any" finite distribution D with probability p=1/2^K(D) [where K(x) = some Kolmogorov complexity measure of x]and then enumerates values based on the distribution D. This universal distribution a finite probability of generating any sequence generated by any other finitely specified distribution.
If we could be come up with a way to eliminate these universal distributions, then a measure of a random sequence's complexity modulus randomness might make sense. I'll wait to see if anyone come up with anything.