# Kolmogorov Complexity of an arbitrary string

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.

• 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.) – usul Sep 15 '13 at 18:03

## 1 Answer

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

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