0
$\begingroup$

Things I understand:

Shannon entropy-

  • is the expected amount of information in an event from that distribution.
  • In game of 20 questions to guess an item, it is the lower bound on the number questions one could ask.

Doubt:

It gives the lower bound on the number of bits needed on average to encode symbols drawn from a distribution.

I don't understand the why it mentions on average. Isn't it just a lower bound. Also, please elaborate on the lower bound if possible.

$\endgroup$
3
$\begingroup$

In game of 20 questions to guess an item, it is the lower bound on the number questions one could ask.

That's incorrect. One could be lucky and get the right answer on the first question. The entropy gives a lower bound on the average number questions one needs to ask.

For example, consider a distribution with three values $(A,B,C)$ with probabilities $(1/2, 1/4, 1/4)$. In this case, the optimum sequence of questions is first ask "Is it A"? If no, ask "Is it B"? To discover the element we need sometimes 1 question, sometimes 2 questions. In average, we need $3/2$ questions. Which (you can check) coincides with the entropy. In this case, the bound is achieved.

$\endgroup$
2
$\begingroup$

To see why there needs to be a notion of lower bound, consider that you need to specify a code. You could choose an arbitrarily inefficient code that takes a ton of bits to encode anything. So this is a statement about how well you can do.

To see why it must be an average, note that in general the length of the encoded sequence of symbols will depend on what symbols actually occur (since each symbol in general will have a different number of bits for its code word.) Since the symbols are randomly drawn, the length of the code will be random.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.