Hacker News Reader

Comment by benchmarkist | Hacker News Reader

Take random bytes from /dev/urandom, encrypt it. There is no way any compressor can reduce the size of that file. I'm pretty sure there is no way the second player can win this game. Actually, the encryption part isn't even necessary. There is no compressor that can reduce the size of a random stream of bytes.

View on HN

There is no general purpose compressor that can achieve compression on all random streams of bytes... but there is a possibility to compress a specific random stream of bytes, if you get lucky

Absolutely! Can this probability be quantified?

You'd have to define what you mean by luck which would be equivalent to choosing some pattern that your compressor can recognize in a random stream of bytes and then computing the probability that pattern appeared in some random byte sequence. It's not a winnable game in any practical sense because whatever compressor you choose the probability of getting a sequence from your opponent that will conform to the patterns recognizable by your compressor is essentially 0.

The encryption part might actually be harmful: for (silly) example, if you encrypt using the Bacon cipher, which turns every letter into five letters all of which are either "a" or "b". :) You'd need to pick an encryption method that doesn't expand the text at all, not even via a header or footer block. Better to stick with bytes generated uniformly at random, in which case you are correct.

[1] - https://en.wikipedia.org/wiki/Bacon%27s_cipher

But you don’t need to compress every possible file to make playing such a game a good idea.

Suppose if you shave 1 bit off of a sample bit stream you win and you lose if that fails. Your compressor looks at the first 2 bits and if it starts 11 it starts with 1 and otherwise it starts 0 then the bit stream. Now you have a 1 in 4 chance to compress a random string by 1 bit and. A 3 in 4 chance of making it longer by 1 bit.

It’s ultimately not about compression but what odds are worth it.

Reply on news.ycombinator.com