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

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

<p>Also, <em>at least</em> $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$.</p>

CC BY-SA 3.0
2013-09-15T14:30:28.837Z
Is $|x|$ here $\log_2n$?
Turbo
CC BY-SA 3.0
2013-09-15T14:34:55.017Z
@JAS When $x$ is a string, $|x|$ is the number of terms in $x$.
Juho
CC BY-SA 3.0
2013-09-15T14:45:16.487Z
@JAS No, for example $|10100|=5$.
Juho
CC BY-SA 3.0
2013-09-15T14:48:29.390Z
$\lceil\log_2x\rceil$
Turbo
CC BY-SA 3.0
2013-09-15T15:19:04.873Z
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
CC BY-SA 3.0
2013-09-15T17:03:56.923Z
@Subhayan Actually, we come to the conclusion that *at least* one string is incompressible. But as you can see if you play around a little with different values of $n$ for small $c$, there are many strings with high Kolmogorov complexity.
Juho
CC BY-SA 3.0
2013-09-15T13:14:21.673Z
2013-09-15T13:14:21.673Z
Juho
<p>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$.</p>

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

CC BY-SA 3.0
2013-09-15T18:03:44.353Z
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
<kolmogorov-complexity>
Kolmogorov Complexity of an arbitrary string
Subhayan
# Kolmogorov Complexity of an arbitrary string

(Asked by: username_0 on 2013-09-15)

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.

**Tags:** kolmogorov-complexity
> **Comments:**
> **username_1**: 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.)  

---

## 1 answers

### Answer by username_2 on 2013-09-15. Score: 5 | Accepted 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$.

> **Comments:**
> **username_3**: Is $|x|$ here $\log_2n$?  
> **username_2**: @JAS When $x$ is a string, $|x|$ is the number of terms in $x$.  
> **username_2**: @JAS No, for example $|10100|=5$.  
> **username_3**: $\lceil\log_2x\rceil$  
> **username_0**: 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?  
> **username_2**: @Subhayan Actually, we come to the conclusion that *at least* one string is incompressible. But as you can see if you play around a little with different values of $n$ for small $c$, there are many strings with high Kolmogorov complexity.  

---

