Entropy of a four-symbol discrete memoryless source
BlinkNBuild practice problem · GATE standard, authored and verified in-house
A discrete memoryless source emits four symbols with probabilities $$\tfrac{1}{2},\quad \tfrac{1}{4},\quad \tfrac{1}{8},\quad \tfrac{1}{8}.$$
The entropy of the source, in bits per symbol, is ________.
Show the step-by-step derivation
Answer
1.75 bits/symbol bits/symbol
Step-by-step derivation
- Entropy is the average information content per symbol: $$H = \sum_{i} p_i \log_2\!\left(\frac{1}{p_i}\right) = -\sum_i p_i \log_2 p_i .$$
- All four probabilities are exact powers of two, so each logarithm is an integer: $$\log_2\!\tfrac{1}{1/2} = 1,\quad \log_2\!\tfrac{1}{1/4} = 2,\quad \log_2\!\tfrac{1}{1/8} = 3.$$
- Form the weighted sum term by term: $$H = \tfrac{1}{2}(1) + \tfrac{1}{4}(2) + \tfrac{1}{8}(3) + \tfrac{1}{8}(3).$$
- Evaluate each term: $$H = 0.5 + 0.5 + 0.375 + 0.375 = \mathbf{1.75\ \text{bits/symbol}}.$$
- Why this matters. A fixed-length code would need $\lceil\log_2 4\rceil = 2$ bits per symbol. Entropy says $1.75$ is achievable, and because every probability is a power of two, a Huffman code ($0$, $10$, $110$, $111$) hits that bound exactly - average length $\tfrac12(1)+\tfrac14(2)+\tfrac18(3)+\tfrac18(3) = 1.75$ bits. A $12.5\%$ saving, with no loss. ✓
The trap this question is built around
Answering $2$ bits by computing $\log_2 4$. That is the entropy of a uniform four-symbol source, which is the maximum. Any departure from uniformity reduces entropy - that headroom is exactly what compression exploits.