Question

The frequency of occurrence of 8 symbols (a-h) is shown in the table below. A symbol is chosen and it is determined by asking a series of "yes/no" questions which are assumed to be truthfully answered. The average number of questions when asked in the most efficient sequence, to determine the chosen symbol, is ___________ (rounded off to two decimal places). 

 

Hint:

The average number of yes/no questions needed to identify an item from a set with a known probability distribution is given by the entropy of the distribution. The formula is $H = \sum p_i \log_2(1/p_i)$. This is a fundamental concept from information theory.

Answer 1

Correct Answer: 1.97

To find the average number of yes/no questions needed to determine the chosen symbol, we use the concept of entropy in information theory.

Entropy \(H\) is calculated by: 

\(H = -\sum_{i=1}^{n} p_i \log_2 p_i\)

where \(p_i\) is the probability of symbol \(i\) and \(n\) is the total number of symbols.

The probabilities are:

Symbol	Probability
a	1/2
b	1/4
c	1/8
d	1/16
e	1/32
f	1/64
g	1/128
h	1/128

Calculating each term:

• \(-\left(\frac{1}{2}\log_2 \frac{1}{2}\right) = 0.5 \)
• \(-\left(\frac{1}{4}\log_2 \frac{1}{4}\right) = 0.5\)
• \(-\left(\frac{1}{8}\log_2 \frac{1}{8}\right) = 0.375\)
• \(-\left(\frac{1}{16}\log_2 \frac{1}{16}\right) = 0.25\)
• \(-\left(\frac{1}{32}\log_2 \frac{1}{32}\right) = 0.15625\)
• \(-\left(\frac{1}{64}\log_2 \frac{1}{64}\right) = 0.09375\)
• \(-\left(\frac{1}{128}\log_2 \frac{1}{128}\right) = 0.0625\)
• \(-\left(\frac{1}{128}\log_2 \frac{1}{128}\right) = 0.0625\)

Summing up all these values gives the entropy:

\(H = 0.5 + 0.5 + 0.375 + 0.25 + 0.15625 + 0.09375 + 0.0625 + 0.0625 = 1.96875\)

Thus, the average number of questions is 1.97, which fits within the given range [1.97, 1.97].