GATE 2023 EC Q.65: solution and answer

GATE 2023 · ECQ.65 · 2 marks · NAT

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

GATE 2023 EC question 65: A table with two rows. — Figure from the GATE 2023 EC paper. It is part of the question.

Answer and solution

ANSWER

The average number of yes/no questions is $\overset{ˉ}{L} = 1.984375 \approx 1.98$ .

Official answer: 1.97 to 1.99Source: Official answer key, GATE 2023 EC (IIT Kanpur)

Each yes/no question gives at most 1 bit, so the most efficient questioning scheme is an optimal binary prefix code (Huffman code). The average number of questions equals the average codeword length $\overset{ˉ}{L}$ of that code.
The probabilities $\frac{1}{2}, \frac{1}{4}, \frac{1}{8}, \frac{1}{16}, \frac{1}{32}, \frac{1}{64}, \frac{1}{128}, \frac{1}{128}$ sum to $1$ , and each one is a negative integer power of 2 (dyadic).
Huffman merging: the two least likely symbols $g, h$ merge to $\frac{1}{128} + \frac{1}{128} = \frac{1}{64}$ . This joins $f$ ( $\frac{1}{64}$ ) to give $\frac{1}{32}$ , then $e$ gives $\frac{1}{16}$ , and so on up to $1$ . The tree is a single chain, so the codeword lengths are $1, 2, 3, 4, 5, 6, 7, 7$ for $a, b, c, d, e, f, g, h$ .
Check: for a dyadic source the length is exactly $- lo g_{2} p_{i}$ (for $g$ and $h$ , $- lo g_{2} \frac{1}{128} = 7$ ), so $\overset{ˉ}{L}$ equals the entropy $H$ and the code meets the lower bound.
$\overset{ˉ}{L} = \frac{1}{2} (1) + \frac{1}{4} (2) + \frac{1}{8} (3) + \frac{1}{16} (4) + \frac{1}{32} (5) + \frac{1}{64} (6) + 2 \cdot \frac{1}{128} (7)$
$\overset{ˉ}{L} = 0.5 + 0.5 + 0.375 + 0.25 + 0.15625 + 0.09375 + 0.109375 = 1.984375$
Rounded to two decimal places, the average number of questions is $\approx 1.98$ (inside the official range 1.97 to 1.99).

KEY IDEA

The most efficient yes/no questioning scheme is the Huffman code. Its average length is the expected number of questions, and for a dyadic source it equals the entropy $H = \sum p_{i} lo g_{2} \frac{1}{p _{i}}$ .

WATCH OUT FOR

Giving the entropy of a source that is not dyadic, or assuming a fixed-length code with 3 questions for 8 symbols. Another slip is giving both of the two rarest symbols length 6 instead of 7.

From the GATE 2023 EC paper. Every question of this paper · Download the full paper · All 9 Information theory questions, with notes

GATE 2023 EC Q.65: solution and answer

Answer and solution

More Information theory questions