Kolmogorov Complexity - Compression

Compression

It is straightforward to compute upper bounds for – simply compress the string with some method, implement the corresponding decompressor in the chosen language, concatenate the decompressor to the compressed string, and measure the length of the resulting string.

A string s is compressible by a number c if it has a description whose length does not exceed . This is equivalent to saying that . Otherwise, s is incompressible by c. A string incompressible by 1 is said to be simply incompressible – by the pigeonhole principle, which applies because every compressed string maps to only one uncompressed string, incompressible strings must exist, since there are bit strings of length n, but only 2n − 1 shorter strings, that is, strings of length less than n, (i.e. with length 0,1,...,n − 1).

For the same reason, most strings are complex in the sense that they cannot be significantly compressed – is not much smaller than, the length of s in bits. To make this precise, fix a value of n. There are bitstrings of length n. The uniform probability distribution on the space of these bitstrings assigns exactly equal weight to each string of length n.

Theorem: With the uniform probability distribution on the space of bitstrings of length n, the probability that a string is incompressible by c is at least .

To prove the theorem, note that the number of descriptions of length not exceeding is given by the geometric series:

There remain at least

bitstrings of length n that are incompressible by c. To determine the probability, divide by .