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.

  • 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, 2013 at 18:03

1 Answer 1


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

  • $\begingroup$ Is $|x|$ here $\log_2n$? $\endgroup$
    – Turbo
    Sep 15, 2013 at 14:30
  • $\begingroup$ @JAS When $x$ is a string, $|x|$ is the number of terms in $x$. $\endgroup$
    – Juho
    Sep 15, 2013 at 14:34
  • 2
    $\begingroup$ @JAS No, for example $|10100|=5$. $\endgroup$
    – Juho
    Sep 15, 2013 at 14:45
  • $\begingroup$ $\lceil\log_2x\rceil$ $\endgroup$
    – Turbo
    Sep 15, 2013 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, 2013 at 15:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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