- #1

- 2

- 0

What is the probability that I can compress it by k bits?

A colleague assures me that the largest possible fraction of random inputs that would compress by e.g. 32 bits would be 2^(-32).

I am struggling to cope with this.

I can see that if I have n bits, then there are 2^n possible arrangements of inputs.

If it compresses by 32 bits then there are 2^(n-32) possible arrangements of outputs.

Hence the fraction that can compress by 32 bits is 2^(n-32)/ 2^n = 2^(-32), but I fail to see what randomness has to do with this - it is true of any n bits.

Does anybody have any idea where I can start to calculate the probability that random data can be compressed by k bits?