The average number of compressible strings in a random set of random strings

Question

In the book Elements of Information Theory (p.446), it is stated:

...although there are some simple sequences, most sequences do not have simple descriptions. Similarly, most integers are not simple. Hence, if we draw a sequence at random, we are likely to draw a complex sequence. The next theorem shows that the probability that a sequence can be compressed by more than k bits is no greater than 2−k.

[snip latex Theorem and Proof]

Thus, most sequences have a complexity close to their length. For example, the fraction of sequences of length n that have complexity less than n − 5 is less than 1/32.

So, the answer I'm looking for looks something like:

For some given set and string length, for a random set of random strings, the number of compressible strings in that set will be on average X percent of that set.

Where X may be 0.0001% or 0.00002193487% or 0.000000009% or something more specific.

Answer 1

The answer is less than $2^{n-k}$ of the sequences of length $n$ have complexity less than $<n-k.$ Due to the uniformity assumption on these sequences we just count.

Consider all short programs of bitlength $<n-k.$ Even if all represented sequences of length $n$ the total number of such programs (starting with the empty program) is $$1+2+2^2+..+2^{n-k-1}<2^{n-k}.$$

To clarify,the number of compressible strings by $k$ bits in a the set of length $n$ bits is $2^{n-k}$, their relative number is $2^{-k}$ and their percentage is $100\times 2^{-k}.$ So for each fixed $k$ and all $n$ you get a constant. For example the percentage of strings of length $n$ which are compressible by $k=3$ is $100\times 2^{-3}=12.5\%,$ those compressible by $10$ bits have percentage $100\times 2^{-10}=0.09765625 \%.$