2

I've often seen as an explanation for shanon entropy that it represents "the average number of yes/no questions needed to find out which state a given system is in."

This works very well for a system having an even number of possible states, but if I try to do this with let's say, 3 possible states all equiprobable I don't find this to be true. Indeed, using the entropy, $ H = \sum_{n = 1}^{3}\frac{1}{3}\log_2(\frac{1}{3}) = 1.58$ I find an average number of 1.58 yes/no questions. If I encode the $1^{st}$ state as 0, the $2^{nd}$ state as 1 and the $3^{rd}$ as 00, the average number of bits (questions) that I need to characterize the system is $\frac{4}{3}=1.33$.

Did I make a mistake somewhere or does it mean that this explanation with the yes/no questions is just a way to simplify things ?

Johncowk
  • 123
  • the average number of bits to encode the strings is approximately equal to the Shannon entropy -- see section on Huffman codes at Cover and Thomas, for instance. – Daniel S. Sep 09 '20 at 11:01
  • https://en.wikipedia.org/wiki/Shannon%E2%80%93Fano_coding – Daniel S. Sep 09 '20 at 11:05

2 Answers2

0

The expected code length of a Shannon-Fano code is

$ \mathbb {E} L=\sum _{i=1}^{n}p_{i}l_{i}\leq \sum _{i=1}^{n}p_{i}(-\log _{2}p_{i}+1)=-\sum _{i=1}^{n}p_{i}\log _{2}p_{i}+\sum _{i=1}^{n}p_{i}=H(X)+1.$

Note that the bound has a "+1" -- this is in agreement with your computations

http://en.wikipedia.org/wiki/Shannon%E2%80%93Fano_coding

Note that Shannon-Fano codes are not optimal, but Huffman codes are. For Huffman codes, see

https://en.wikipedia.org/wiki/Huffman_coding

Daniel S.
  • 823
0

First, your proposed encoding $A\to 0$, $B \to 1$, $C\to 00$ attains a coding length below the entropy, which should be impossible.

The problem is that your encoding is practically useless, because it's not "uniquely decodable": if you receive $00$ you cannot know if the input was $AA$ or $C$.

Then you need to do something like $A\to 0$, $B \to 10$, $C\to 11$ , which has an average coding length of $5/3=1.666$ , above the entropy ($H=1.585$). This is to be expected.

And if you code each value isolated, then, yes, you cannot perform better than that . But you can code several values together (code "the extension of the source"), and approach the entropy.

Consider for example a group of $n=5$ values. There are $3^5=243$ equally probable joint values. Because $243 < 256 = 2^8$, you can code this with group with $8$ yes-no questions.

Hence, with this simple scheme, you'd need to ask $8$ questions to discover $5$ values, which gives a coding length $8/5=1.6$, near the entropy.

The above is not optimal (see Huffman coding) but you get the idea.

leonbloy
  • 63,430