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

<p>Consider all short programs of bitlength $&lt;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}&lt;2^{n-k}.$$</p>

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

CC BY-SA 3.0
2016-10-01T04:53:23.933Z
Thank you for the answer. Could you possibly provide that as some approximate constant? Presumably, like phi (1.618...), that sequence converges on some constant ratio, where < n - k represents some rational proportion of the set? Or am I mistaken, and no such rational, aproximate constant exists?
John
CC BY-SA 3.0
2016-10-01T09:09:05.530Z
See my edit, the percentage depends on $k$.
kodlu
CC BY-SA 3.0
2016-10-01T18:20:51.623Z
Oh, so for any length set and any length binary string, half of those strings will be compressible by one bit and one quarter will be compressible by two bits and one eighth will be compressible by three bits, on average?
John
CC BY-SA 3.0
2016-10-01T20:24:11.047Z
yes but its an upper bound, so less than one eighth are compressible by 3 bits,, which is the same as more than seven eighths can't be compressed by 3 bits.
kodlu
CC BY-SA 3.0
2016-10-01T02:16:46.233Z
2016-10-01T09:07:30.987Z
2016-10-01T09:07:30.987Z
kodlu
<p>In the book Elements of Information Theory (p.446), it is stated:</p>

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

<p><em>[snip latex Theorem and Proof]</em></p>

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

<p>So, the answer I'm looking for looks something like:</p>

<p><strong><em>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.</em></strong></p>

<p>Where X may be 0.0001% or 0.00002193487% or 0.000000009% or something more specific.</p>

<cc.complexity-theory><it.information-theory><randomness>
The average number of compressible strings in a random set of random strings
John
# The average number of compressible strings in a random set of random strings

(Asked by: username_0 on 2016-09-30)

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.

**Tags:** cc.complexity-theory, it.information-theory, randomness


---

## 1 answers

### Answer by username_1 on 2016-10-01. Score: 3 | Accepted answer

The answer is less than $2^{n-k}$ of the sequences of length $n$ have complexity less than $

Consider all short programs of bitlength $

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

> **Comments:**
> **username_0**: Thank you for the answer. Could you possibly provide that as some approximate constant? Presumably, like phi (1.618...), that sequence converges on some constant ratio, where < n - k represents some rational proportion of the set? Or am I mistaken, and no such rational, aproximate constant exists?  
> **username_1**: See my edit, the percentage depends on $k$.  
> **username_0**: Oh, so for any length set and any length binary string, half of those strings will be compressible by one bit and one quarter will be compressible by two bits and one eighth will be compressible by three bits, on average?  
> **username_1**: yes but its an upper bound, so less than one eighth are compressible by 3 bits,, which is the same as more than seven eighths can't be compressed by 3 bits.  

---

