Sometimes randomness spits out what we call patterns. 123456 seems like a pattern to us, and our beloved compression algos we wrote. But 123456 is just as random as any combo. I think. Right?

Related thinking, Sean Carroll on TED- Arrow of Time http://y2u.be/WMaTyg8wR4Y He says there's 'more' or 'less' entropy, but is there really such a thing? Rolling 6666666 on a dice, and we scream luck! But rolling 3164536 should be just as likely/unlikely.

For lack of a better idea, that's how I once tested a toy PRNG I programmed. Feed output to rzip, check compression level, tweak a few knobs till it compresses worst.

However, that's not a good guaranty of true randomness. Encrypted data (for decent encryption algorithms) has high entropy just as well, even if the plaintext is non-random.

On the other hand, if you have a truly random process with very low probability of occuring, its output would indeed compress well via, for example, RLE.

The property of not being compressable is about both entropy and uniform distribution. See also http://en.wikipedia.org/wiki/Randomness_extractor