From: shenkin@avogadro.barnard.columbia.edu (Peter S. Shenkin)
Subject: Re: Interpreting Shannon
Organization: Dept. of Chem, Barnard College, Columbia U, New York
Distribution: bionet
Date: Thu, 8 Oct 1992 17:49:04 GMT
X-Posted-From: avogadro.barnard.columbia.edu
NNTP-Posting-Host: sol.ctr.columbia.edu

[[ Pardon me if you've seen this twice;  there were a couple of misprints
in the previous version, which I cancelled. ]]

 tolman%asylum.cs.utah.edu@cs.utah.edu (Kenneth Tolman) writes:
>Consider a source with 4 random possible outputs:  A, BJD, DHFDD, and HJKHHKJH
>Assume the probability of each to be:
>
>DHFDD       0.5
>BJD         0.25
>A           0.125
>HJKHHKJH    0.125
>
>Then the entropy of this source is 1.75 bits, with Shannon's measure.

Correct;  you can think of it as 1.75 bits per source output, where
each source output is an emission of one of the four values shown.

>Now, if the source produces one of these in particular, say BJD, how do
>we measure the amount of information produced?  Would it not be the 
>-log(0.25), or in general -log p(i)?  Is this correct?

No, it would not.  It is 1.75 bits.  You go from an uncertainty of 
1.75 bits to an uncertainty of 0.

>So in general, given any random source, the amount of information created would
>be -log (probability of occurance of output)

No.  But parenthetically, as Press et. al. make clear in "Numerical 
Recipes," you can say that the "value" of an answer is -log( its 
a-priori probability ).  Thus, if I tell you that the weather in Arizona 
today is "hot and dry", that answer is less valuable than the statement 
(if correct) that the weather today in the the Amazon rain forest 
is "hot and dry."  Similarly, if I tell you that "the output was DHFDD," 
that answer is less valuable than the statement, if true, that "the 
output was A".

Then, Press et. al. go on to say, the Shannon entropy (they don't use 
this term) can be thought of as the value of the *question*, "What is 
the output?"  We take this as the average value of all the answers, 
which is - Sum ( p log2 p ).

>Now, the Kolmogrov complexity of an object is its minimal description in bits,
>so we could consider the entropy of any particular sequence as a combination
>of Shannon and Kolmogrov...

I don't know anything about the Kolmogorov complexity, but if your 
definition is correct it appears to be the same as the Shannon entropy 
of the source for this example.

You can think of the Shannon entropy as the average number of bits 
necessary to resolve the ambiguity of a single output from the source, 
given an optimal strategy.  For instance, suppose you are holding the 
answer in your hand, and suppose I know the a-priori probabilities of 
the possible answers, and devise the most efficient possible set of 
yes-no questions I could ask to determine what answer you hold.  First 
I would ask:

	Q1: Is it DHFDD?  I would be right 50% of the time;  thus, 
	half the time I would know the answer after asking exactly 
	one question.

If I was wrong, I would ask:

	Q2: Is it BJD?  I would get the answer right in exactly
	two questions 1/4 of the time -- because I'd be wrong in 
	Q1 half the time, and of this half I'd be right in Q2 
	half the time.

If I was wrong in Q2, which would happen 1/4 of the time, overall, 
I would ask:

	Q3: Is it A?  Whether I guessed right or not, I would know 
	the answer, since at the Q3 stage the only possibilities 
	are A and HJKHHKJH.  Thus I would know the answer having asked 
	exactly 3 questions 1/4 of the time.

On average, how many questions would I need?  Taking the weighted 
average:

	1*(1/2) + 2*(1/4) +3*(1/4) = 1.75 
	= Shannon entropy of the source.

If I were to shuffle the questions and ask them in a different order, 
I would no longer have an optimal strategy, and the average number of 
questions I would need to get the right answer would no longer be equal 
to the Shannon entropy.

I believe this example is correct, and I like it very much!

	-P.
-- 
************************f*u*cn*rd*ths*u*cn*gt*a*gd*jb*************************
Peter S. Shenkin, Department of Chemistry, Columbia Univ.,  New York, NY 10027
(212)854-8402    shenkin@avogadro.barnard.columbia.edu   shenkin@cunixf.BITNET
*********************** UNIX:  the wave of the present ***********************