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
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 idea behind this question
Entropy measures the average information per symbol, $H = -\sum p_i\log_2 p_i$ bits. It is largest when every symbol is equally likely - $\log_2 M$ for $M$ symbols - and smaller whenever some symbols are more likely than others. The gap is what a compression code such as Huffman coding can save.
Try a variation
What is the entropy of a three-symbol source with probabilities $\tfrac12, \tfrac14, \tfrac14$?
Show the answer
Answer: $1.5$ bits
$\tfrac12 \cdot 1 + \tfrac14 \cdot 2 + \tfrac14 \cdot 2 = 1.5$ bits.
Other mistakes to avoid
- Dropping the minus sign, which gives a negative entropy.
- Using $\log_{10}$ or $\ln$ and forgetting that the answer is then in other units, not bits.