Entropy in Information Theory

Entropy: Measuring Information and Uncertainty

Entropy is the most fundamental concept in information theory — it quantifies how much "information" or "surprise" a source produces. Claude Shannon borrowed this term from thermodynamics in 1948, recognizing that information and physical disorder share deep mathematical similarities. Understanding entropy is essential for grasping data compression limits, channel capacity, and optimal coding.

What Is Information?

Think of it this way: if someone tells you "the sun will rise tomorrow," that contains almost zero information — you already knew it would happen. But if they say "there will be a solar eclipse tomorrow," that is highly informative because it was unexpected. Information theory formalizes this intuition: rare events carry more information than common ones.

The information content (self-information) of an event with probability p is:

I(x) = -log₂(p) bits

Examples:

• Fair coin showing heads (p = 0.5): I = -log₂(0.5) = 1 bit
• Rolling a 6 on a fair die (p = 1/6): I = -log₂(1/6) = 2.585 bits
• A certain event (p = 1): I = -log₂(1) = 0 bits (no surprise!)
• A very rare event (p = 0.001): I = -log₂(0.001) = 9.97 bits (very informative!)

Shannon Entropy: Average Information

Entropy is the expected (average) information content of a source:

H(X) = -Σ p(xᵢ) × log₂(p(xᵢ)) bits/symbol

For a source with alphabet {x₁, x₂, ..., xₙ} and probabilities {p₁, p₂, ..., pₙ}:

H(X) = -(p₁log₂p₁ + p₂log₂p₂ + ... + pₙlog₂pₙ)

Example: English text has 26 letters. If all were equally likely (p = 1/26):

• H = log₂(26) = 4.7 bits/letter

But English letters are NOT equally likely (E is common, Z is rare). The actual entropy of English is approximately 1.0-1.5 bits/letter — much lower because of predictability (redundancy).

Properties of Entropy

1. Non-negativity: H(X) ≥ 0. You cannot have negative information.

2. Maximum entropy: H(X) ≤ log₂(N) for N symbols. Maximum occurs when all symbols are equally likely (maximum uncertainty).

3. Additivity: For independent sources X and Y: H(X,Y) = H(X) + H(Y)

4. Conditioning reduces entropy: H(X|Y) ≤ H(X). Knowing something about Y can only reduce our uncertainty about X, never increase it.

Binary Entropy Function

For a binary source with P(0) = p and P(1) = 1-p:

H(p) = -p×log₂(p) - (1-p)×log₂(1-p)

This function has these key properties:

• H(0) = H(1) = 0 (certain outcome → no information)
• H(0.5) = 1 bit (maximum uncertainty for binary source)
• Symmetric: H(p) = H(1-p)

The binary entropy function appears repeatedly in communication theory — it describes the capacity of binary channels and the entropy of any two-outcome experiment.

Joint and Conditional Entropy

Joint entropy of two variables X and Y: H(X,Y) = -Σᵢ Σⱼ p(xᵢ,yⱼ) × log₂(p(xᵢ,yⱼ))

Conditional entropy — uncertainty about X given knowledge of Y: H(X|Y) = H(X,Y) - H(Y)

Chain rule: H(X,Y) = H(X) + H(Y|X) = H(Y) + H(X|Y)

Mutual Information

Mutual information measures how much knowing Y tells you about X:

I(X;Y) = H(X) - H(X|Y) = H(Y) - H(Y|X) = H(X) + H(Y) - H(X,Y)

Key properties:

• I(X;Y) ≥ 0 (knowing Y never hurts)
• I(X;Y) = 0 if and only if X and Y are independent
• I(X;X) = H(X) (a variable tells everything about itself)

Channel capacity is the maximum mutual information over all input distributions: C = max_{p(x)} I(X;Y)

Entropy and Data Compression

Shannon's source coding theorem states:

No lossless compression can achieve fewer than H bits/symbol on average.

This makes entropy the fundamental limit of data compression:

• Source with H = 3 bits/symbol → optimal compression achieves 3 bits/symbol
• If a code achieves 3.1 bits/symbol, it is nearly optimal
• Anything below 3 bits/symbol is impossible without losing information

Example: A source produces symbols A, B, C, D with probabilities 0.5, 0.25, 0.125, 0.125:

• H = -(0.5×(-1) + 0.25×(-2) + 0.125×(-3) + 0.125×(-3)) = 1.75 bits/symbol
• Huffman coding achieves exactly 1.75 bits/symbol for this source (optimal!)

Entropy Rate and Redundancy

Entropy rate for correlated sources accounts for dependencies between consecutive symbols: H∞ = lim_{n→∞} H(Xₙ|X₁,...,Xₙ₋₁)

Redundancy measures how much above the minimum a source operates: R = log₂(N) - H(X)

English text has high redundancy (about 3.5 bits/letter out of 4.7 possible are redundant), which is why English can be compressed by roughly 75%.

Practical Significance

Entropy appears throughout communication engineering:

• Source coding: Entropy sets the compression limit (Huffman, arithmetic coding)
• Channel capacity: C = max I(X;Y) — maximum achievable rate
• Cryptography: Maximum entropy = maximum security (unpredictability)
• Machine learning: Cross-entropy loss function for classification
• Statistical testing: Entropy measures distribution uniformity

Key Takeaways

1. Entropy H(X) = -Σp(x)log₂p(x) quantifies the average uncertainty/information of a source, measured in bits per symbol.
2. Maximum entropy occurs when all outcomes are equally likely — maximum unpredictability.
3. Conditional entropy H(X|Y) ≤ H(X) — knowledge can only reduce uncertainty, never increase it.
4. Mutual information I(X;Y) measures the information shared between variables — it equals channel capacity when maximized.
5. Shannon's source coding theorem makes entropy the unbreakable lower bound on lossless compression.
6. Redundancy (the gap between maximum possible entropy and actual entropy) is what makes both compression and error correction possible.