Entropy/entropy example 3

Consider the unit square representing the space $\Omega$, where the probability is the Lebesgue measure (i.e., the surface area), and the partition $\mathcal A$ into four sets $A_i$ of probabilities $\frac18, \frac14, \frac18, \frac12$, respectively, as shown in Figure <ref>F4</ref>.

Figure 1: The partition $\mathcal A$.

The information function equals $-\log_2\left(\frac 18\right) = 3$ on $A_1$ and $A_3$, $-\log_2\left(\frac 14\right) = 2$ on $A_2$ and $-\log_2\left(\frac 12\right) = 1$ on $A_4$. The entropy of $\mathcal A$ equals

$$H(\mathcal A) = \frac18\cdot3 + \frac14\cdot2 + \frac18\cdot3 + \frac12\cdot1 = \frac74.$$

The arrangement of questions that optimizes the expected value of the number of questions asked is the following (see Figure <ref>F5</ref>):

• Question 1. Are you in the left half?

The answer no, locates $\omega$ in $A_4$ using one bit. Otherwise the next question is:

• Question 2. Are you in the central square of the left half?

The yes answer locates $\omega$ in $A_2$ using two bits. If not, the last question is:

• Question 3. Are you in the top half of the whole square?

Now yes and no locate $\omega$ in $A_1$ or $A_3$, respectively. This takes three bits.

Figure 2: The arrangement of binary questions.

In this example the number of questions equals exactly the information function at every point and the expected number of question equals the entropy $\frac 74$. There does not exist a better arrangement of questions. Of course such accuracy is possible only when the probabilities of the sets $A_i$ are powers of $\frac12$.