A discrete memoryless source X has four symbols x₁, x₂, x₃, x₄ with probabilities P(x₁) = 0·4, P(x₂) = 0·3, P(x₃) = 0·2, P(x₄) = 0·1 respectively.
I. Calculate H(x).
II. Find the amount of information contained in the messages x₁, x₂, x₁, x₃ and x₄, x₃, x₃, x₂ and compare with the H(x) obtained in part (I).
10 marks · directive: Calculate and compare
The core of a good answer
H(X) = −Σ p log₂ p ≈ 1.846 bits/symbol, so a four symbol message carries 4H ≈ 7.39 bits on average; the message x₁x₂x₁x₃ carries 6.70 bits (below average, as it uses likely symbols) and x₄x₃x₃x₂ carries 9.70 bits (above average, as it uses unlikely symbols).
An outline written by upsc.help, not an official UPSC answer; every fact checked by a separate review. How we work
What the question asks
The question separates two ideas: entropy, which is the average information per symbol, and self information of a particular message, which depends on its probability. For a memoryless source the information of a sequence is the sum of the self informations of its symbols.
Answer outline
Introduction
Self information I(xᵢ) = −log₂ P(xᵢ) bits. Since the source is memoryless, P(message) is the product of symbol probabilities and its information is the sum.
Step 1: Self information of each symbol
- I(x₁) = −log₂ 0.4 = 1.322 bits
- I(x₂) = −log₂ 0.3 = 1.737 bits
- I(x₃) = −log₂ 0.2 = 2.322 bits
- I(x₄) = −log₂ 0.1 = 3.322 bits
Step 2: Entropy, part I
- H(X) = Σ P(xᵢ) I(xᵢ)
- = 0.4 × 1.322 + 0.3 × 1.737 + 0.2 × 2.322 + 0.1 × 3.322
- = 0.5288 + 0.5211 + 0.4644 + 0.3322
- H(X) ≈ 1.846 bits/symbol
Step 3: Message x₁, x₂, x₁, x₃
- P = 0.4 × 0.3 × 0.4 × 0.2 = 0.0096
- I = −log₂ 0.0096 ≈ 6.70 bits
- Per symbol: 6.70/4 ≈ 1.68 bits
Step 4: Message x₄, x₃, x₃, x₂
- P = 0.1 × 0.2 × 0.2 × 0.3 = 0.0012
- I = −log₂ 0.0012 ≈ 9.70 bits
- Per symbol: 9.70/4 ≈ 2.43 bits
Step 5: Comparison with H(X)
- Average information in any four symbol message = 4H(X) ≈ 7.39 bits
- Message 1: 6.70 bits < 7.39 bits, because it is built from the more probable symbols
- Message 2: 9.70 bits > 7.39 bits, because it contains the least probable symbol x₄ and two x₃
- Entropy is an average over all messages; individual messages can carry more or less
Conclusion
H(X) ≈ 1.846 bits/symbol; message one carries 6.70 bits and message two 9.70 bits, compared with an average of 7.39 bits for four symbols. Check: the maximum entropy for four symbols is log₂ 4 = 2 bits, and H is below it because the probabilities are unequal.
Examples and data to cite
- The message x₁x₂x₁x₃ is eight times as probable as x₄x₃x₃x₂ (0.0096/0.0012 = 8), so it carries exactly log₂ 8 = 3 bits less information.
- Shannon introduced the entropy measure in A Mathematical Theory of Communication (1948).
Facts to remember
- Self information I(x) = −log₂ P(x) bits; rarer events carry more information.
- Entropy H(X) = −Σ P(xᵢ) log₂ P(xᵢ), the average self information.
- For a memoryless source, information of a sequence is the sum of symbol informations.
- 0 ≤ H(X) ≤ log₂ M, with equality at the upper bound for equiprobable symbols.
- Numbers recomputed in Python: H = 1.84644, I₁ = 6.7027, I₂ = 9.7027 bits.