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).
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).
Show 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.
Updated On: Feb 12, 2026
Show Solution
Verified By Collegedunia
Correct Answer: 1.97
Solution and Explanation
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.
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.
Was this answer helpful?
0
0
Top GATE EC Electronics and Communication Engineering Questions
- In a semiconductor, if the Fermi energy level lies in the conduction band, then the semiconductor is known as
- For an intrinsic semiconductor at temperature $T=0K$, which of the following statement is true?
- A series RLC circuit has a quality factor $Q$ of 1000 at a center frequency of $10^{6}$ rad/s. The possible values of $R$, $L$ and $C$ are
For a MOS capacitor, $V_{fb}$ and $V_t$ are the flat-band voltage and the threshold voltage, respectively. The variation of the depletion width ($W_{\text{dep}}$) for varying gate voltage ($V_g$) is best represented by
- Consider a narrow band signal, propagating in a lossless dielectric medium $(\varepsilon_r = 4, \mu_r = 1)$, with phase velocity $v_p$ and group velocity $v_g$. Which of the following statement is true? ($c$ is the velocity of light in vacuum.)
View More Questions
Top GATE EC Signals and Systems Questions
- Consider a narrow band signal, propagating in a lossless dielectric medium $(\varepsilon_r = 4, \mu_r = 1)$, with phase velocity $v_p$ and group velocity $v_g$. Which of the following statement is true? ($c$ is the velocity of light in vacuum.)
- Consider a system with input x(t) and output y(t) = x(e^t). The system is
- Let $m(t)$ be a strictly band-limited signal with bandwidth $B$ and energy $E$. Assuming $\omega_0=10B$, the energy in the signal $m(t)\cos \omega_0 t$ is
- The Fourier transform \(X(\omega)\) of \(x(t)=e^{-t^{2}}\) is \[ X(\omega)=\sqrt{\pi}\,e^{-\tfrac{\omega^{2}}{4}}. \]
- In the table shown below, match the signal type with its spectral characteristics.
\[ \begin{array}{|l|l|} \hline \text{Signal type} & \text{Spectral characteristics} \\ \hline (i) \; \text{Continuous, aperiodic} & (a) \; \text{Continuous, aperiodic} \\ \hline (ii) \; \text{Continuous, periodic} & (b) \; \text{Continuous, periodic} \\ \hline (iii) \; \text{Discrete, aperiodic} & (c) \; \text{Discrete, aperiodic} \\ \hline (iv) \; \text{Discrete, periodic} & (d) \; \text{Discrete, periodic} \\ \hline \end{array} \]
View More Questions
Top GATE EC Questions
- Consider the discrete-time system below with input \( x[n] \) and output \( y[n] \). In the figure, \( h_1[n] \) and \( h_2[n] \) denote the impulse responses of LTI Subsystems 1 and 2, respectively. Also, \( \delta[n] \) is the unit impulse, and \( b>0 \).
Assuming \( h_2[n] \neq \delta[n] \), the overall system (denoted by the dashed box) is _________.
\includegraphics[width=0.5\linewidth]{17.png} “I cannot support this proposal. My ___________ will not permit it.”
Courts : _________ :: Parliament : Legislature ; (By word meaning)
What is the smallest number with distinct digits whose digits add up to 45?
- In a class of 100 students, (i) there are 30 students who neither like romantic movies nor comedy movies, (ii) the number of students who like romantic movies is twice the number of students who like comedy movies, and (iii) the number of students who like both romantic movies and comedy movies is 20. How many students in the class like romantic movies?
View More Questions