How many "compressible" strings are there?

Let's say that a string of length $N$ is "compressible" iff its Kolmogorov complexity is less than $N$. To keep it simple, we can assume binary strings for this.

It is easy to see that almost all binary strings of length $N$ are incompressible by using the pigeonhole principle.

So my question is, how many strings of length $N$ are compressible?

In particular, let's assume that $K(S)$ is the Kolmogorov complexity of binary string $S$, which is of length $N$. Then I have the following three questions:

• Of the $2^N$ binary strings $S$ of length $N$, how many have $K(S) \leq N-1$?

• Of the $2^N$ binary strings $S$ of length $N$, how many have $K(S) \leq N/2$?

• Of the $2^N$ binary strings $S$ of length $N$, how many have $K(S) \leq \log N$?

All of the above are for sufficiently large $N$.

A simple counting argument shows that the number of strings of length $N$ such that $K(S) \leq M$ is at most $2^{M+1}$.

Conversely, considering the program $\Pi$ that gets an integer $r$ and a string $x$, and outputs $x$ together with $r$ many zeroes. Going over all strings of length $\ell$, this gives us $2^\ell$ many strings whose complexity is at most $\ell + O(\log N)$. Choosing $\ell = M - O(\log N)$, this shows that the number of strings of length $N$ such that $K(S) \leq M$ is at least $2^M/N^{O(1)}$.

This answers your first two questions up to a small multiplicative error. I suspect that the answer to the third one depends heavily on $N$.

StackExchange Computer Science Q#117289, answer score: 6