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?