6
$\begingroup$

For an arbitrary string sampled from $\{0,1\}^n$, what would be the probability that the string has a Kolmogorov Complexity $\geq$ length of the string, $n$.

In other words, how many strings are there in the above set that satisfy the definition of random, as defined in Kolmogorov Complexity.

$\endgroup$
  • 1
    $\begingroup$ I think an issue might be, for any given $n$, we probably can't say much more than that one string is definitely incompressible. Maybe a good way to phrase the question is as follows? "What is $\lim_{n \to \infty} \#\{$ incompressible strings of length $n\} / 2^n$?" (Or limsup.) $\endgroup$ – usul Sep 15 '13 at 18:03
5
$\begingroup$

A string $x$ is $c$-compressible if $K(x) \leq |x| + c$. If $x$ is not compressible by $1$, $x$ is said to be incompressible (or random, if you will).

There are $2^n$ bit strings of length $n$, and there are $\sum_{i=0}^{n-1} 2^i = 2^n-1$ descriptions that are of length less than $n$. Because each description describes at most one string, there is at least one incompressible bit string for each length $n$.

Also, at least $2^n-2^{n-c+1}+1$ strings of length $n$ are incompressible by $c$. Once again, at most $2^{n-c+1}-1$ strings of length $n$ are $c$-compressible, because we have at most that many descriptions of length at most $n-c$. Then the remaining $2^n-(2^{n-c+1}-1)$ strings are incompressible by $c$.

$\endgroup$
  • $\begingroup$ Is $|x|$ here $\log_2n$? $\endgroup$ – T.... Sep 15 '13 at 14:30
  • $\begingroup$ @JAS When $x$ is a string, $|x|$ is the number of terms in $x$. $\endgroup$ – Juho Sep 15 '13 at 14:34
  • 2
    $\begingroup$ @JAS No, for example $|10100|=5$. $\endgroup$ – Juho Sep 15 '13 at 14:45
  • $\begingroup$ $\lceil\log_2x\rceil$ $\endgroup$ – T.... Sep 15 '13 at 14:48
  • $\begingroup$ awesome :) but can you explain a bit more on why $2^n - 2^{n-c+1} + 1$.. i used to know this result, but something does not seem right.. if we have $c = 1$, we come to the conc. that just 1 string is incompressible by $c$, but if a bin. string is incompressible by $c'$, it's 1s complement should also be incompressible by the same... i can sense i am making some kind of trivial mistake.. can you help me out on this? $\endgroup$ – Subhayan Sep 15 '13 at 15:19

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.