- #1
karamand
- 6
- 0
Suppose that I have n bits of random data.
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?
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?