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

The "most efficient sequence" of yes/no questions to determine a symbol from a set with known probabilities corresponds to a Huffman code. The average number of questions is the average code length of the Huffman code for these symbols.
The problem can also be solved by calculating the entropy of the source, which gives the theoretical lower bound on the average number of bits (or yes/no questions) needed. For probabilities that are powers of 1/2, Huffman coding achieves this bound.
Step 1: List the symbols and their probabilities ($p_i$). a: 1/2 b: 1/4 c: 1/8 d: 1/16 e: 1/32 f: 1/64 g: 1/128 h: 1/128
Note that the probability for symbol h must also be 1/128 to make the sum of probabilities equal to 1. $\frac{1}{2}+\frac{1}{4}+\frac{1}{8}+\frac{1}{16}+\frac{1}{32}+\frac{1}{64}+\frac{1}{128}+\frac{1}{128} = \frac{64+32+16+8+4+2+1+1}{128} = \frac{128}{128}=1$.
Step 2: Calculate the entropy H(X). The entropy is given by the formula $H(X) = -\sum_{i=1}^{n} p_i \log_2(p_i) = \sum_{i=1}^{n} p_i \log_2(1/p_i)$. $\log_2(1/p_i)$ represents the number of bits needed to encode symbol i.
$H = (\frac{1}{2}\log_2 2) + (\frac{1}{4}\log_2 4) + (\frac{1}{8}\log_2 8) + (\frac{1}{16}\log_2 16) + (\frac{1}{32}\log_2 32) + (\frac{1}{64}\log_2 64) + (\frac{1}{128}\log_2 128) + (\frac{1}{128}\log_2 128)$.
$H = (\frac{1}{2}\cdot 1) + (\frac{1}{4}\cdot 2) + (\frac{1}{8}\cdot 3) + (\frac{1}{16}\cdot 4) + (\frac{1}{32}\cdot 5) + (\frac{1}{64}\cdot 6) + (\frac{1}{128}\cdot 7) + (\frac{1}{128}\cdot 7)$.
$H = \frac{1}{2} + \frac{2}{4} + \frac{3}{8} + \frac{4}{16} + \frac{5}{32} + \frac{6}{64} + \frac{7}{128} + \frac{7}{128}$.
$H = 0.5 + 0.5 + 0.375 + 0.25 + 0.15625 + 0.09375 + 0.0546875 + 0.0546875$.
$H = 1 + 0.375 + 0.25 + 0.15625 + 0.09375 + 0.109375$.
$H = 1.984375$.
The average number of questions is 1.984375.
Rounding off to two decimal places, we get 1.98.