[107785] in Cypherpunks
Redundancy and Randomness [Information Theory]
daemon@ATHENA.MIT.EDU (mgraffam@idsi.net)
Sat Jan 23 19:42:13 1999
From: mgraffam@idsi.net
Date: Sat, 23 Jan 1999 19:21:44 -0500 (EST)
To: cypherpunks@toad.com
Reply-To: mgraffam@idsi.net
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.
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.
I'm thinking of compression.
An ideal compression algorithm that compressed a message down to its
essential entropy would have 0 redundancy (by definition) .. and while
it would not be 'philosophically random' (how could a deterministic
algorithm get randomness from ordered bits?) it seems that such a
compression function's output would be indistinguishable from true
randomness.
Michael J. Graffam (mgraffam@idsi.net)
"86% of conspiracy theories have some basis in truth... but, oddly enough,
it's that last 14% that usually gets you killed."
--Talas (http://cadvantage.com/~algaeman/conspiracy/public.htm)
