Hacker News Reader

Comment by haberman | Hacker News Reader

Mike's contest didn't limit the total size of the (input, random) data file, so you could make it arbitrarily large to make the cost of the decompression program arbitrarily small.

View on HN

It is not possible, without some amount of luck. The reason is, that you can think of the data + decompressor as a program which contains the data as some binary blob. There are less than 2^s different possible executables, where s is the filesize of the compressor together with the compressed data. And therefore 2^s different outputs. On the other hand, there are 2^l different original files (l is the filesize). Therefore only a few files can be compressed to a smaller file size. To be precise, you can compress at best 2^s files out of the 2^l ones by l-s bits.

Thinking a bit further, for a file of length l, the probability getting a file that can be compressed is smaller than

\sum_{k=1}^{l-1} 2^{-k} [1]

which approaches 1 for l against infinity. ( So just based on the upper limit, your odds seem to get better for longer programs. :)

[1]rendered formula for the equation (hope this works): http://latex.codecogs.com/gif.latex?\sum_{k=0}^{l-1}%202^{-k...

If the data file is truly random, then there is no decompression program + compressed file that would be smaller than the original random file. That's the entire point.

I'm not saying you could! I am only rebutting your earlier line of reasoning.

IF you could write an algorithm that would compress a specific block of random data by any non-zero percentage, and IF you can make the original random data arbitrarily large, THEN the overall size of the code to implement this algorithm would not matter, because you could amortize it over an arbitrarily large random data file.

However I am not claiming that such an algorithm to compress a specific block of random data exists! However other people are arguing that this is indeed theoretically possible: http://news.ycombinator.com/item?id=5025527

What if the rng generates a file with massive redundancy by chance. Doesn't make it any less "truly random."

> [...] the contestant will send me a decompressor and a compressed file, which will together total in size less than the original data file, and which will be able to restore the compressed file to the original state.

Then how would you find redundancy in arbitrarily large random data?

See my comment http://news.ycombinator.com/item?id=5025527 This is a misunderstanding of the pigeonhole principle, which only applies to a specific compression algorithm. It does NOT apply if you get to write a custom algorithm for this data set.

There are always redundancies in random data. If you can pick them out ahead of time with a custom algorithm it's certainly possible to "compress" it.

Edit: I think I may be wrong here.

Except, that 'specific compression algorithm' could be "attach an x86 program to your compressed data, which I will run", which then covers all algorithms you might care to submit.

...except in this case a complex custom algorithm will make the decompressor bigger which will count against your total size.

Reply on news.ycombinator.com