Compression of Random Data is Impossible?

Question

A few days ago this appeared on HN http://www.patrickcraig.co.uk/other/compression.htm. This refers to a challenge from 2001 - where someone was offering a prize of \$5000 for any kind of reduction to the size of randomly generated data (the entrance cost would be \$100 and the contestant could choose the file-size).

I understand the result which shows it is impossible to compress all files of size >= N to a smaller size (http://en.wikipedia.org/wiki/Kolmogorov_complexity#Compression).

But in the challenge question the idea is to only compress a single randomly generated file. A simple approach is to find $l$ the longest recurring substring in a file and substitute that with $s$ the shortest non-occuring substring which would give a saving of $l-s$ (since the decompresser only needs one l,s pair).

To obtain an approximation for the single shortest non-occurring substring as Usul pointed using the approximation for the coupon problem: $$E(t) = nlog(n) + \gamma n + (1/2n)$$

In this case $t$ is the number of possible substrings and using bytes for simplicity that's respectively:

275 megabytes for 3 byte strings ($n=256^3$)

91 gigabytes for 4 byte strings ($n=256^4$)

The probability of a recurring substring in the random data is equivalent to the birthday problem over the size of the random data, $p = 1-e^{-((n^2)/2d)}$, for example at 91 gigabytes one can expect to find a recurring 9 byte substring with: $d=256^9$, $n = 91*1024^3$. $p \approx .636$

With $5000:100$ odds it should be possible to optimize a little more. Of course the cost of sed delimiters will be 3 bytes, if the cost of the command counts this method isn't enough to be successful - but this is without doing anything particularly clever.

Am I missing something (It would seem that the majority of random data should not be in fact incompressible)? What is the basis on which someone offers such a challenge and presumes it is entirely unwinnable for the player?

---

Edit (updated calculations up top as well): Also I think its possible to have a savings of precisely $l-s$ without having to pay for a delimiter. This is because it is known that substring $s$ did not exist prior to insertion - therefore the pair can be arranged with $sl$ contiguously written in memory and either the length of $s$ is known ahead of time (by estimating the shortest substring) or the next byte following $s$ in the file does not collide with the first byte of $l$ with at least probability $255/256$ (this gets better actually by having a choice which non-occuring $s$ to substitute for which recurring $l$).

Answer 1

Here's the Kolmogorov complexity argument that @YuvalFilmus mentions in his answer.

Your input here is a sed script of some size plus an input file of some size. Say the total size of the sed script plus the file is $n$ bits.

There can be only $2^n$ inputs of size $n$ bits. Even if I let you have a sed script of less than $n$ bits (and don't charge you for telling me how long the input is) there can only be $2^{n+1}$ possible inputs. But there are $2^{n+8}$ possible strings of length $n+8$ bits, so you can produce at most $1/128$th of the possible $2^{n+8}$ bit strings. That's less than .01, so paying 50:1 my expected value for the bet would be positive (about 0.60). (And that's only giving you 1 byte to play with.)

In short, random strings that are compressible at all must be extremely rare.

Why your scheme is broken

Your probability calculations look fine to me. And the idea of a birthday attack is so appealingly clever, it took me quite a while to see the real problem.

Your basic scheme doesn't compress.

Suppose you find a 4-byte substring that doesn't occur in the original string, and an 8-byte substring that occurs twice in the original string.

Then you are going to produce a "compressed" string of length $n$ bytes - 8 bytes - 8 bytes + 4 bytes + 4 bytes, plus a sed replacement script which must be of length at least 4 bytes + 8 bytes. Add that all together and we get $n+4$.

If the longer string is length $l$ and repeats $r$ times and the shorter string is of length $s$ then in general your scheme reduces the string length by

$$ (l-s) r - (l+s).$$ So $l=7$, $r=3$, $s=4$ "works" (saves 2 bytes), but the probability of finding a 7 byte substring that repeats 3 times is infinitesimal.

Answer 2

It is always possible to compress a single file. Given a file $f$, here is an encoding scheme which is especially good for compressing $f$. The empty string is used to encode $f$. Every other string encodes itself. We have succeeded reducing $f$ to zero bytes!

What is the catch? We didn't take into account the length of the decompression procedure. When we do take it into account, the problem goes away. The Kolmogorov complexity of a string $f$ is the size of the minimal problem generating $f$ in some fixed programming language. A simple counting argument shows that most strings of length $n$ cannot be generated by programs of length less than $n-1$, and at least one string requires a program of length at least $n$; we call such a string Kolmogorov random.

In your case, you need a compression/decompression procedure which works for several different files at once, which are not known in advance. The situation is slightly different but the conclusions are similar.

Answer 3

You have to be really careful with these kind of proposals to check your constants and arguments. And it's hard to get motivated to check the proposal carefully when we know it's proven impossible to work in general. But anyway, let's run some asymptotics for your proposal.

What is a guess at the length of the shortest non-occurring substring? Well, it will be just about $\log n$ (some details below). This boils down to a coupon collector's type problem. Now, what is a guess at the length of the longest repeated substring? Well, it will be about $2\log n$ (details below). This time it boils down to the birthday paradox, as you said.

This shows that at best you would hope to save $\log n$ bits with your replacement. But I am pretty sure you would lose these $\log n$ bits because you would need to delimit your strings and program and to do that requires some other unique non-occurring string, or some other "escape character" type strategy. So I hope this illustrates why these sorts of proposals are delicate/tricky.

---

Computing these probabilities and string lengths accurately is actually quite tricky, but this is an optimistic estimate that I think should be about right.

Coupon: Let's say we want the shortest non-occurring substring to have length $m$. Optimistically, we can divide the string into $n/m$ disjoint segments of length $m$ each, and just require that not all possible strings of length $m$ appear as one of these segments. This will be a bit more optimistic than reality because of the possibility that a string occurs as an overlap between two segments. But anyway there are $2^m$ strings of length $m$, so by the coupon collectors problem we expect to try $2^m \log(2^m) = m2^m$ independent trials until we collect them all. Thus the number of disjoint segments $n/m$ can be as large as about $m 2^m$, which we solve for $n = m^2 2^m$, or $m \approx \log n - 2\log\log n$.

Birthday: If we look at all the strings of length $m$, there are about $2^m$ possible strings. If we pretend for optimism that we get $n$ independent tries to draw a substring of length $m$ (one for each index a substring could start at), then we expect a number of collisions $1 = {n \choose 2} \frac{1}{2^m} \approx \frac{n^2}{2 2^m}$, or $m \approx 2\log n$.

Answer 4

It is in fact easy to prove that the average bit length under any compression scheme over all input strings of length $n$ cannot be less than $n-1$.

---

To see why, note that you can arrange the set of output strings first in lexicographic order and then by length, and then for each chain of strings (namely where each is a prefix of the next) add $1$ bit to each of them to make them no longer a chain (each is not a prefix of the next). Now you have a compression scheme that takes at most $1$ bit more than the original scheme but is also a prefix-free code. Let $T$ be the binary tree representing the codes (output strings) for all input strings of length $n$. The claim is that the average code length is at least $n$.

The first obvious way to prove it is by structural induction. Let $f(k)$ be the minimum average code length for a tree with $k$ leaves. Then I claim that $f(k) \ge \log(k)$ (binary logarithms). To prove it, for each $k$ there is some tree $T$ that has average code length $f(k)$, so letting $p,q$ be the sizes of the child subtrees of $T$, we have $k = p+q$ and $k·f(k) = k + p·f(p)+q·f(q)$ $\ge k + p·\log(p)+q·\log(q)$ by structural induction. And by Jensen's $p·\log(p)+q·\log(q)$ $\ge 2·\frac{p+q}{2}·\log(\frac{p+q}{2})$ $= k·(\log(k)-1)$, and thus $f(k) \ge \log(k)$, completing the structural induction.

A second non-obvious but elegant discrete way is to prove the following about an optimal tree (namely with minimum average code length): (1) Every internal node must have two children, otherwise you can eliminate that node to shorten the codes for all the descendant leaves. (2) There cannot be two leaves whose depths differ by at least two, otherwise you can modify it to create a better tree. (Move the /\ containing the deeper leaf to the position of the shallower leaf, and check that the three affected codes have total length shortened.) From (1) and (2) it is clear that every code in the optimal tree with $k$ leaves has length at least $\log(k)$.

---

Thus even when we do not count the EOF marker needed to signal the end of the file, no compression scheme can compress input strings of length $n$ such that the average compressed length is less than $n-1$. And the above proof shows that if you require prefix-free encoding then the lower bound is $n$.

And so this means that it is definitely false that the majority of strings can be compressed. Even if you take advantage of an EOF marker (which is essentially cheating), the above shows that you cannot do better than $1$ bit on average.

In fact, that is a very tight bound if your objective is to only compress strings of a fixed size $n$, and I shall describe an encoding that achieves $(1-2^{-n})$-bit compression on average: Simply delete all leading zero bits. $\frac12$ of the strings will have their first bit removed, and $\frac14$ will have their second bit removed, and so on. Thus the average number of bits removed from all the codes is $\frac12+\frac14+\frac18+\cdots+\frac1{2^n}$, as claimed.