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:

If $P_i=2^{-k_i}$, the optimal yes/no questions equal exactly $k_i$ per symbol, and the average equals $\sum P_i k_i = H$ when $k_i=-\log_2 P_i$ are integers.

Answer 1

For the most efficient sequence (optimal binary decision tree/Huffman code), the number of yes/no questions for a symbol equals its codeword length $l_i$.
Since all probabilities are powers of $\tfrac12$, we have $l_i=-\log_2 P_i$:
$l(a)=1,\ l(b)=2,\ l(c)=3,\ l(d)=4,\ l(e)=5,\ l(f)=6,\ l(g)=7,\ l(h)=7$.
Average number of questions $\,\bar{L}=\sum_i P_i l_i$:
$\bar{L}= \tfrac12(1)+\tfrac14(2)+\tfrac18(3)+\tfrac1{16}(4)+\tfrac1{32}(5)+\tfrac1{64}(6)+\tfrac1{128}(7)+\tfrac1{128}(7)$
$\;\;=0.5+0.5+0.375+0.25+0.15625+0.09375+0.0546875+0.0546875=1.984375\approx 1.98$.
\[ \boxed{1.98} \]