3
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

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

Improve this answer
$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$
    – John
    Oct 1, 2016 at 4:53
  • $\begingroup$ See my edit, the percentage depends on $k$. $\endgroup$
    – kodlu
    Oct 1, 2016 at 9:09
  • $\begingroup$ 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? $\endgroup$
    – John
    Oct 1, 2016 at 18:20
  • $\begingroup$ 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. $\endgroup$
    – kodlu
    Oct 1, 2016 at 20:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.