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$
$\endgroup$
4
-
$\begingroup$ Are you using "standard" Kolmogorov complexity here, or prefix complexity? $\endgroup$– Aubrey da CunhaCommented Aug 29, 2011 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 sCommented Aug 29, 2011 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$– domotorpCommented Aug 31, 2011 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 BiasiCommented Aug 31, 2011 at 10:50
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
2
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$
$\endgroup$
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)$.
