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}$)?

  • $\begingroup$ Are you using "standard" Kolmogorov complexity here, or prefix complexity? $\endgroup$ – Aubrey da Cunha Aug 29 '11 at 19:05
  • $\begingroup$ Actually I was thinking only of Kolmogorov complexity. I was guessing the $2^{n_{o}}$ bound that domotorp mentioned when we consider the universe of all strings. I was not clear if any 'consistent' result for an arbitrary random subset of size $M$ can be produced. However would prefix complexity bring us to a different view point? $\endgroup$ – v s Aug 29 '11 at 21:21
  • $\begingroup$ It certainly would not change the order of magnitude, in fact I think now my answer is a bound for both versions. $\endgroup$ – domotorp Aug 31 '11 at 6:53
  • 1
    $\begingroup$ For every $n$ and every $c$, the probability that a random $n$-bit string $x$ has Kolmogorov complexity $K(x) \geq n-c$ is greater than $1 - \frac{1}{2^c}$ (with $c = n-n_0$). So in a random distribution of $M$ strings, you should expect $\frac{M}{2^(n-n_0)}$ strings with $K(x) \lt n_0$ ... intuitively, there is a very high probability to pick a string with high Kolmogorov complexity. $\endgroup$ – Marzio De Biasi Aug 31 '11 at 10:50

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.

  • $\begingroup$ Could you explain a little about the phrase 'if your program says "of length n, take the xth number"'? $\endgroup$ – v s Aug 29 '11 at 21:24
  • $\begingroup$ You are right, it should be prefix-free there, I corrected it. $\endgroup$ – domotorp Aug 31 '11 at 6:51

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)$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.