From: "Perry E. Metzger" <perry@piermont.com>
Date: Wed, 17 Apr 1996 13:24:14 +0800
To: rick hoselton <hoz@univel.telescan.com>
Subject: Re: why compression doesn't perfectly even out entropy
In-Reply-To: <199604161843.LAA19508@toad.com>
Message-ID: <199604162134.RAA15579@jekyll.piermont.com>
MIME-Version: 1.0
Content-Type: text/plain



rick hoselton writes:
> At 10:07 AM 4/16/96 -0400, Perry E. Metzger wrote:
> 
> >...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...
> 
> But even if it came from a completely random source, it would 
> still make a bad one-time pad.

No it wouldn't. There is a tiny but nonzero probability that xoring
your one time pad with your text will result in a cyphertext equal to,
say, the Bible. Big deal. If the key is really random, the
cryptanalyst has no way to tell what the underlying text was.

> In the context of "fair coin flips" the text of Hamlet is NOT compressible.

Huh?

There is only one context in which things are compressable or not --
is there a smaller representation for them.

> Because no string is more likely than any other.  Any algorithm that could 
> compress that string, will, on the average INCREASE the length of 
> "fair coin flip" strings it tries to compress.

True enough, but the claim was that a random string has no
representation which is smaller than itself.

.pm