Suppose that I have n bits of random data.(adsbygoogle = window.adsbygoogle || []).push({});

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?

**Physics Forums | Science Articles, Homework Help, Discussion**

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Probability of compressing n random bits by k bits

**Physics Forums | Science Articles, Homework Help, Discussion**