Compression of random binary data

[Marko Rauhamaa]

Gregory Ewing <greg.ewing at canterbury.ac.nz>:

> What you *can't* do is compress 16 random decimal digits to less than
> 6.64 bytes.

More precisely:

   Regardless of the compression scheme, the probability of shortening
   the next bit sequence is less than 0.5 if the bits are distributed
   evenly, randomly and independently.

Often the distribution is not even, or there is interdependence between
the bits. Then, a compression scheme can do miracles.


Marko