[107793] in Cypherpunks
Re: Redundancy and Randomness [Information Theory]
daemon@ATHENA.MIT.EDU (Tim May)
Sat Jan 23 21:59:13 1999
In-Reply-To: <Pine.LNX.3.96.990123191136.3911A-100000@albert>
Date: Sat, 23 Jan 1999 18:44:48 -0800
To: cypherpunks@cyberpass.net
From: Tim May <tcmay@got.net>
Reply-To: Tim May <tcmay@got.net>
At 4:21 PM -0800 1/23/99, mgraffam@idsi.net wrote:
>hey everyone..
>
>I've been working on some stuff lately, and it occurred to me that
>it hinges on the assumption that if a message has 0 redundancy, then it
>consists of essentially random bits.
Randomness, compressibility, redundancy, entropy, and predictability are
all intimately related. Cf. any good modern text on information theory,
e.g., Thomas Cover's "Elements of Information Theory," for much discussion
of this.
Using terms I won't define in the detail which is needed for further
analysis, here are some of the basic notions:
* a truly random string (whatever _that_ is) is not generally compressible.
That is, there is no shorter description of the string than the string
itself.
* I said "truly random," even though there is a nonzero chance that a
finite string could be randomly generated and be "31415926535" and be
trivially compressible, or be "attack at dawn" and also be compressible.
(However, a rough measure of the chance of such an expression turning up
when the length is N is 2 exp -N. That is, the number of compressible
sequences or strings drops exponentially in the length of the string.)
>I'm not comfortable with this assumption intuitively, so I was wondering
>if anyone knows of a proof that such a message must be random, or can
>think of an example where this would not be the case.
Interestingly, one can never "prove" that a string (or message) is random.
One can establish grounds for believing this to be so, that the message was
generated from a random-like source (e.g., Johnson noise, radioactive
decay, whatever).
And there's Von Neumann's comment about those who believe in mathematically
generated sequences being random are living in a state of sin.
--Tim May
Y2K -- Where were you when the lights went out?
---------:---------:---------:---------:---------:---------:---------:----
Timothy C. May | Crypto Anarchy: encryption, digital money,
ComSec 3DES: 831-728-0152 | anonymous networks, digital pseudonyms, zero
W.A.S.T.E.: Corralitos, CA | knowledge, reputations, information markets,
Licensed Ontologist | black markets, collapse of governments.
