entropy example 3

From Scholarpedia

< Entropy
Tomasz Downarowicz (2007), Scholarpedia, 2(11):3901. revision #25684 [link to/cite this article]

Curator: Tomasz Downarowicz, Institute of Mathematics Computer Science, Wroclaw University of Technology, Poland

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 1.

Entropy/entropy example 3
Enlarge
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 2):

  • 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.
Enlarge
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.


Invited by: Dr. Eugene M. Izhikevich, Editor-in-Chief of Scholarpedia, the peer-reviewed open-access encyclopedia
Action editor: Dr. Eugene M. Izhikevich, Editor-in-Chief of Scholarpedia, the peer-reviewed open-access encyclopedia
Retrieved from "http://www.scholarpedia.org/article/Entropy/entropy_example_3"
For authors