From: tcmay@got.net (Timothy C. May)
Date: Wed, 17 Apr 1996 05:12:13 +0800
To: cypherpunks@toad.com
Subject: Re: why compression doesn't perfectly even out entropy
Message-ID: <ad99193c040210040b50@[205.199.118.202]>
MIME-Version: 1.0
Content-Type: text/plain


At 2:07 PM 4/16/96, Perry E. Metzger wrote:
>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...

Sure, compressibility is not a determinant of randomness....nothing is,
actually. This is my point about there being no simple definition of
randomness.

However, "most" objects derived from a "random-like process" have no
shorter description than themselves, by a variant of the pigeonhole
principle (i.e., there are more things of some size than descriptions of
less than that size, so most "random" objects, are, perforce, not
describable in short descriptions).

--Tim May

Boycott "Big Brother Inside" software!
We got computers, we're tapping phone lines, we know that that ain't allowed.
---------:---------:---------:---------:---------:---------:---------:----
Timothy C. May              | Crypto Anarchy: encryption, digital money,
tcmay@got.net  408-728-0152 | anonymous networks, digital pseudonyms, zero
W.A.S.T.E.: Corralitos, CA  | knowledge, reputations, information markets,
Higher Power: 2^756839 - 1  | black markets, collapse of governments.
"National borders aren't even speed bumps on the information superhighway."