From: tcmay@got.net (Timothy C. May)
Date: Thu, 21 Sep 95 09:18:02 PDT
To: cypherpunks@toad.com
Subject: Re: Entropy vs Random Bits
Message-ID: <ac86dcbd3d021004c67b@[205.199.118.202]>
MIME-Version: 1.0
Content-Type: text/plain


At 11:50 PM 9/20/95, David Van Wie wrote:
>I've been watching the debate and discussion unfold on usable sources of
>random data from environments, user actions, etc.  I have a vocabulary
>question (and something of a bone to pick as a mathematician and physicist).

Well, I was trained as a physicist also, but am completely comfortable with
the Shannon definition of information-theoretic entropy. In fact, through
my readings about entropy in computations (cites below), I now view
traditional thermodynamic entropy as a special case of information theory!

>Usually, the term "entropy" is being used to characterize one of two
>different things: (i) random data, as in "300 bits of entropy," and (ii) the
>"randomness" of data (i.e. high degree of variance in a statistic drawn from
>it), as in "you can find a lot of entropy in the low order bits of a timed
>interval between keystrokes."  I suspect that there are other shades of
>meaning intended in other uses as well.
>
>This is odd.  The term entropy describes an aspect of thermodynamic
>equlibrium in physical systems.  Although sometimes used as a synonym for
>"random," that definition is vernacular, not technical.  In fact, there is
>no meaningful relationship between "entropy" and random data of the type
>described in the postings related to seed values.  In the presense of a
>perfectly suitable and precise mathematical term (i.e. random), why invent
>new terms?  Why use them to mean at least two different things?

Entropy has been used with an information theory context since the 1950s,
by Claude Shannon and others.

I disagree that there is "no meaningful relationship between "entropy" and
random data of the type described in the postings related to seed values."
The bits of entropy we are talking about are the "bits derived from a
physical process or a user action which are effectively from a random
process."

(Granted, the internal thoughts of a user swirling the mouse around are not
quite as "random" as, say, alpha decay, but for all intents and purposes no
"prediction" can be made of the mouse motions, at certain levels of detail,
and the bits dervived are in fact effectively random. We are not "living in
a state of sin," to paraphrase Von Neumann, in using these bits and
assuming them to be random.)

Good books on the incredibly fascinating aspects of information theory, and
expecially algorithmic information theory:

* Cover and Thomas, "Elements of Information Theory." A good textbook on
information theory, covering gambling (!), prediction, and the
Chaitin-Kolmogoroff outlook.

* Chaitin, Gregory, "Algorithmic Information Theory." A bit dense to read,
and Chaitin has written several more popular accounts for "Scientific
American" and similar places.

* Zurek, Wojciech, editor, "Complexity, Entropy, and the Physics of
Infromation." This collection of great articles shows the role of entropy
in infromation theory, and why the thermodynamic definition is essentially
a variant of the more fundamental information-theoretic definition.

Enjoy!

--Tim May


Notice: With 1000 people on the Cypherpunks list, and many on other lists I
am on, nearly every article I write generates at least one question,
request for more information, dispute with my choice of words, etc. I have
been trying to respond to these, usually privately, but the burden has
become too much, and I no longer plan to respond to trivial or ephemeral
points. If you don't hear from me, this is why. Some requests for pointers
to information will still be handled, but I advise people to learn how to
use the archives and/or search tools.
---------:---------:---------:---------:---------:---------:---------:----
Timothy C. May              | Crypto Anarchy: encryption, digital money,
tcmay@got.net  408-728-0152 | anonymous networks, digital pseudonyms, zero
Corralitos, CA              | knowledge, reputations, information markets,
Higher Power: 2^756839      | black markets, collapse of governments.
"National borders are just speed bumps on the information superhighway."