Randomness goal of compression
n A fully compressed data sequence is
indistinguishable from a random sequence
of 0s and 1s.
n This follows directly from Kolgomorov and
Chaitin’s results.
n From Shannon we also have the result that for
each bit of the stream to have maximal
information it must mimic the tossing of a fair
coin : be unpredictable, random.