Expected values of Kolmogorov complexity in a random sample

Question

Kolmogorov complexity of a string is not computable. However, in a random subset of size $M$ of binary strings of length $n$, how many are expected to have complexity less than some integer $n_{0}$ less than $n$ (as a function of $M$, $n$ and $n_{0}$)?

Answer 1

Kolmogorov complexity is only determined up to some additive constant, so it is not possible to give an exact answer. The bound that I describe here is even weaker.

Of course the expected number can be computed easily once we know how many of the $2^n$ strings have complexity less than $n_0$, so let me answer this. It is usually the first statement about Kolmogorov complexity that this number is at most $2^{n_0}-1$ - since there are only these many strings of smaller length. On the other hand, if your program says "of length $n$, take the $x$th number", then you get $2^{n_0-K(n)-C}$ strings of complexity less than $n_0$, where $K(n)$ is the prefix-free version of Kolmogorov complexity of $n$ (so at most $\log n+\log^* n + O(1)$). In more detail, the string first contains the description of the Turing machine that taken input $px$, where p is the description of a prefix-free program that outputs $n$, outputs the $x$th number of length $n$, which is $O(1)$ bits, and then this is followed by $px$.

Probably it is possible to improve these bounds, but I doubt that you could get an exact answer.

Answer 2

A precise answer can be given. The number of strings of length $n$ with (plain) complexity at most $n_0$ is $2^{n_0 - K(n_0|n)}$, up to a constant factor. Hence any process that randomly chooses a subset will have, with reasonable probability, a $2^{-K(n_0|n) + O(1)}$ fraction of strings of complexity less than $n_0$. To show our our claim, it suffices to show that the number of strings with complexity equal to $k$ is also given by $2^{k - K(k|n)}$. We can show the necessary result by determining the summation of this value over $k$ from 1 up to $n_0$. To show this, we use an additivity result for plain complexity (due to B. Bauwens and A. Shen. An additivity theorem for plain Kolmogorov complexity. Theory of Computing Systems, 52(2):297-302, Feb 2013), $$ C(a,b) = K(a|C(a,b)) + C(b|a,C(a,b)) + O(1). $$ Here $K(\cdot)$ denotes prefix-free Kolmogorov complexity. Choosing $a = n$, we observe that for each $n$-bit string $b$ of complexity $k$ we have $$ k = C(b) = C(n,b) + O(1) = K(n|k) + C(b|n,k) + O(1). $$ Hence, for each such $b$ we have $C(b|n,k) = k - K(n|k)+O(1)$. Let $k' = k - K(n|k)$. Now one can observe that there are at most $O(2^{k'})$ such strings $b$, and each of the lexicographically first $2^{k'}$ strings of length $n$ satisfy $C(b|n,k) \le k' + O(1)$. Thus $\Omega(2^{k'})$ of them satisfy $C(b|n,k) = k' + O(1)$.