4
$\begingroup$

Preamble

There's this great YouTube video explaining the entropy of a probability distribution using the idea of "what is the minimum number of questions I need to ask?".

So as an example, if I draw from a 4:2:1:1 distribution of A, B, C, D and need to ask questions to determine what letter I have drawn, the most efficient way of doing so is:

  1. Is it an A? (if yes, 1 question was required, that's $(-\log_{2}P(A))$ questions)
  2. Is it a B? (if yes, 2 questions were required, that's $(-\log_{2}P(B))$ questions)
  3. Is it a C? (if yes, 3 questions were required, that's $(-\log_{2}P(C))$ questions)

So then the entropy is just the expected number of questions we need to ask (dropping base 2 for ease of notation):

$$ - P(A)\log(P(A)) - P(B)\log(P(B)) - P(C)\log(P(C)) - P(D)\log(P(D)) $$

Simple!

Actual question

The analogy is not enough to cover all bases though. What if I have a 3:1 distribution of A, B? I know how to calculate the entropy using the formula, but I can't work it into the minimum questions analogy. Is there a way to do so? Is there another analogy or intuitive model I can use to deal with this case?

Note: This related question is very similar but not quite asking the same thing.

$\endgroup$
1

2 Answers 2

2
$\begingroup$

I feel like I'm really close but just need to bridge a final gap.


The challenge with having a 3:1 split is that the entropy ends up being something like 0.811, and we can't ask a fractional number of questions, which is why the yes/no framework falls apart.

Consider a sequence of As and Bs.

...AABAAABABBAAABAAAA

If the ratio were 1:1 I would just have to tell you what each symbol is: A or B. and the entropy would be 1 (1 bit of information per symbol). But now I can take advantage of the fact that there are more A's than B's. I can provide a different piece of information. That is "How many A's are there before the next B appears?". For the sequence above I would say: "4,3,0,1,3,..." (parsing it in reverse order).

Of course, what I'm saying is not in bits, it's in base 10. And I say a different number each time. So I need to find the expectation value of the number of bits required. Let's do that in steps. First we write down the probability of $n$ A's followed by 1 B

$$ P(n) = (0.75)^n\cdot 0.25 $$

Then the expectation value is:

$$ E_{n \sim P}[n] = 0.25\sum_{i}^\infty {i(0.75)^i} $$

where we've taken the 0.25 out of the sum. Now we apply the sum of geometric series identity (with a slight modification)

$$ \sum_{i}^\infty ir^i = \frac{1}{(1-r)^2} $$

(I figured that out by modifying the proof for standard sum of geometric series so you might want to check it for yourself). So in applying that we get

$$ \begin{aligned} E_{n \sim P}[n] &= \frac{0.25}{(1-0.75)^2} \\ & = \frac{1}{0.25} \end{aligned} $$

And so the expected number of bits required is: $-\log(0.25)$. Now the other important aspect, is how often I need to provide this information. Well because B occurs 25% of the time, then I need to provide this information for 1 in every 4 symbols on average. So the number of bits required per symbol is $-0.25\log(0.25)$.

But we know the full entropy is $-0.25\log(0.25) - 0.75\log(0.75)$. What about the second part? Well, we could have gone back and applied similar logic How many B's are there before the next A appears?. This is also an interesting question, because although I have to provide you with information more often on average (75% of the time, instead of 25% of the time), the number of bits required to encode that information is expected to be just $-\log(0.75)$ (which is smaller than $-\log(0.25)$).

Cool so to summarise... If I use method 1:

"How many A's are there before the next B appears?"

the average number of bits required per symbol is $-0.25\log(0.25) = 0.5$

And if I use method 2:

"How many B's are there before the next A appears?"

the average number of bits required per symbol is $-0.75\log(0.75) = 0.311$

Now I don't know how to bridge the gap to explain why summing these two quantities is the right answer. Shouldn't I just choose the cheapest method, that is method 2?

$\endgroup$
2
  • $\begingroup$ How did you go from $E_{n\sim P}[n] = 1/0.25$ to $-\log 0.25$ ? $\endgroup$
    – Ron
    Mar 10, 2021 at 4:06
  • $\begingroup$ @Ron first we take the log to get the number of bits. Then we write $1/0.25$ as $0.25^{-1}$. So it's $\log(0.25^{-1})$, and because $\log(A^B) =B\log(A)$ we can write it as $-\log(0.25)$ $\endgroup$ Mar 10, 2021 at 13:05
1
$\begingroup$

Interesting enough, I was thinking yesterday on a very similar question after watching a very similar youtube video. While I can not provide a real answer, I would like to share my attempts.

Assume there are 100 distinguishable entities that can be in three distinguishable states A, B, and C. It is known that 90 entities are in state A and 5 entities are in state B and 5 in state C.

The Shannon entropy is $H=.9*log(.9)+.05*log(.05)+.05*log(.05)=0.5689956$, where $log$ is base 2.

Now both videos seem to claim that the $H$ is the average number of yes-/no-questions necessary to determine the state of a given entity.

The value of $H$ is between 0 and 1, which I interpret that there must be cases where no question needs to be asked. I can only think of one probability distribution where no question is necessary, that is when the all the probability mass is on one state. In that case, the entropy is also 0. However, the entropy is continously increasing, while as soon the probability distribution is not "singular", the average number of questions must be 1 or more.

Attempt 1

So maybe $H$ is not the average number of yes-/no-questions asked, but the average number of yes-/no-questions answered with no? If our search algorithm would be

  1. is the entity in state A?
  2. is the entity in state B?
  3. is the entity in state C?,

then in 90% of the case no question would have been answered "no". Combined with the probabilities for the other questions, we get $0.1*1 + 0.1*0.5*2=0.2$, which is much lower than $H$.

Attempt 2

So maybe $H$ is not the average number of yes/no-questions asked for one given entity, but the average number of questions necessary to determine the states of all entities, divided by the number of entities? This would us allow to incorporate the knowledge of previous entities. The search algorithm could then look like this:

  1. The distribution $P$ is $(0.9, 0.05, 0.05)$.

iterate over all entities:

  1. If $P$ is singular, no question necessary
  2. Question: is the entity in the state with the highest proability?
  3. If no: ask a second question.
  4. recalculate $P$, taking into account that some entities have been removed.

The mean over all entities of the questions asked in this scheme is way above 1.

Attempt 3

So maybe the original interpretation of the claim in the videos is correct, but the equivalence is only up to some factor or transformation?

Here is a chart comparing the average number of questions (x axis, "nsearches") to $H$. Each dot is a different probability distribution (so it is not (0.9, .05, .05) anymore, but moves to a more uniform distribution to the right).

H vs. #searches for different probability distributiosn

Both functions seem to capture the same behaviour (increasing entropy), but their relationsship remains unclear to me.


So these are my attempts. I am very interested in a verified interpretation / intuition of Shannon entropy in terms of "search costs".

$\endgroup$
1
  • $\begingroup$ Your attempts inspired me and I posted my own answer which I think nearly answers it. See if you can finish it off! $\endgroup$ Jan 21, 2021 at 18:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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