From: "Perry E. Metzger" <perry@piermont.com>
Date: Wed, 17 Apr 1996 03:07:09 +0800
To: tcmay@got.net (Timothy C. May)
Subject: Re: why compression doesn't perfectly even out entropy
In-Reply-To: <ad987fec02021004063f@[205.199.118.202]>
Message-ID: <199604161407.KAA15253@jekyll.piermont.com>
MIME-Version: 1.0
Content-Type: text/plain



Timothy C. May writes:
> Well, I don't view any of the "simple definitions" of randomness as
> especially useful; that is, the simple definitions have a kind of
> circularity (implicit in the points we both make). For example, "an object
> is "random" if it has no shorter description than itself," the classic
> Solomonoff-Kolmogorov-Chaitin definition, is quite elegant, but doesn't
> help much in many cases.

Except that it goes against our normal definitions of random in a
crypto context. A string that is compressable might still be
random. There is no reason you can't have a string of 20 1 bits in
a row in a perfectly random sequence, for example. Usually, random
sequences are non-compressable, but it is possible (though very
improbable) for Hamlet to appear out of a random number generator,
and it is of course quite compressable...

Perry