Is There An Algorithmic Complexity Of A Random Distribution

Question

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.

Answer 1

If we accept such a definition „the Kolmogorov complexity of a probability distribution $P$ is the shortest program that outputs $P(x)$ to precision $q$ on input $\left \langle x, q \right \rangle$” (from example 7, p. 16 here) we need neither rational weights nor finitely-many outcomes. E.g. a Poisson distribution fits here. Of course, we need all the parameters of the distribution to be computable numbers.

The key point is that the Kolmogorov complexity of a probability distribution is just a special case of the Kolmogorov complexity of a function. If we want to extend our notions to continuous distributions, we first have to have a good notion for a continuous function (see e.g. here).

Answer 2

The short answer is it depends on what one means by extending Kolmogorov complexity. The details are below. First, when I say Kolmogorov complexity, I will mean prefix-free complexity since that is what I am most familiar with.

Countable setting

First, to use Kolmogorov complexity as usual, one must consider discrete distribution which assign rational weights to finitely-many outcomes. (We may assume the outcomes are just the first $n$ numbers.) The main point is that the set of objects you are considering must be countable (with a computable enumeration). Their complexity is just the complexity of their codes. (For example, the distribution which assigns the weights $p_1, \ldots, p_n$ to the first $n$ numbers may be coded by the triple $(p_1,\ldots,p_n)$ which may be coded as a natural number $c$. The complexity of the distribution is just the the complexity of $c$). This approach has been used to measure the complexity of finite graphs (search for "Kolmogorov complexity graphs" on a search engine). As for uniqueness, Kolmogorov complexity is only unique up to an additive constant, the same is true in this case. The choice of how to code the distributions would only change the complexity function up to an additive constant.

Uncountable setting

Now, if you want to deal with an uncountable collection of distributions (notice that even the set of all weighted coins is uncountable), one cannot talk about Kolmogorov complexity, per se, but one can talk about related concepts. On Cantor space $\{0,1\}^\mathbb{N}$, one usually talks about the initial segment complexity of a bit string.

These ideas can be extended to other spaces as well. See the paper "K-trivality in computable metric spaces" which defines K-triviality on computable metric spaces. (The space of distributions---probability measures---of a computable metric space is also a computable metric space.)

Answer 3

Joshep, You can find an information measure of complexity for continuous distribution in http://www.mdpi.com/1099-4300/18/3/72/htm

Kind Regards

Nelson Fernández