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**

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**