Joint and Conditional Entropy — Mathematics Knowledge System

Overview

Joint entropy H(X,Y) measures uncertainty in two random variables together. Conditional entropy H(Y|X) = H(X,Y) - H(X) measures remaining uncertainty in Y given knowledge of X. The chain rule H(X,Y) = H(X) + H(Y|X) is fundamental. These quantities satisfy: H(Y|X) <= H(Y) (conditioning reduces entropy), with equality iff X and Y are independent.

Intuition

H(X,Y) is like H of a single variable (X,Y) viewed as a pair. H(Y|X) asks: on average, how much uncertainty is left about Y after you learn X? If X = Y (identical), then H(Y|X)=0 (learning X tells you everything about Y). If X and Y are independent, H(Y|X) = H(Y) (learning X gives no info about Y). Mutual information I(X;Y) = H(Y) - H(Y|X) = reduction in Y's entropy due to X.

Formal Definition

Definition

H(X,Y) = -sum_{x,y} p(x,y) log p(x,y). H(Y|X) = -sum_{x,y} p(x,y) log p(y|x) = H(X,Y) - H(X). Chain rule: H(X_1,...,X_n) = sum_{i=1}^n H(X_i | X_1,...,X_{i-1}). Data processing inequality: if X->Y->Z is a Markov chain, then I(X;Z) <= I(X;Y).

H(X,Y) = -\sum_{x,y} p(x,y)\log p(x,y)

Joint entropy

H(Y|X) = H(X,Y) - H(X)

Conditional entropy

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

Mutual information

Notation

Notation	Meaning
$H(X,Y)$	Joint entropy of X and Y
$H(Y\|X)$	Conditional entropy of Y given X
$I(X;Y)$	Mutual information between X and Y

Theorems

Theorem 1: Subadditivity of Entropy

H(X,Y) <= H(X) + H(Y), with equality iff X and Y are independent. Equivalently, H(Y|X) <= H(Y): conditioning cannot increase entropy.

Worked Examples

1
H(X,Y) = -3*(1/3)*log_2(1/3) = log_2(3) ≈ 1.585 bits.
$H(X,Y) = \log_2 3$
2
P(X=0)=2/3, P(X=1)=1/3. H(X) = -(2/3)log(2/3)-(1/3)log(1/3) ≈ 0.918.
$H(X) \approx 0.918$
3
H(Y|X) = H(X,Y) - H(X) ≈ 1.585 - 0.918 = 0.667 bits.
$H(Y|X) \approx 0.667$

✓ Answer

H(X,Y) = log_2(3) ≈ 1.585, H(Y|X) ≈ 0.667 bits.

Practice Problems

Mediumapplication

If X and Y are independent with H(X)=2 bits and H(Y)=3 bits, find H(X,Y) and I(X;Y).

Common Mistakes

Common Mistake

Thinking H(Y|X) = H(Y) - H(X).

H(Y|X) = H(X,Y) - H(X), not H(Y) - H(X). Mutual information I(X;Y) = H(Y) - H(Y|X) = H(X)+H(Y)-H(X,Y).

Quiz

Which inequality always holds?

H(Y|X) >= H(Y)H(X,Y) >= H(X) + H(Y)H(Y|X) <= H(Y)I(X;Y) < 0

Historical Background

Joint and conditional entropy appear in Shannon's foundational 1948 paper 'A Mathematical Theory of Communication.' Shannon developed these quantities to characterize the information content of stochastic sources and the capacity of communication channels. The chain rule for entropy mirrors the chain rule for probability.

1948
Shannon defines joint entropy, conditional entropy, and mutual information in his seminal paper
Claude Shannon

Summary

H(X,Y) = -sum p(x,y) log p(x,y). H(Y|X) = H(X,Y) - H(X).
Chain rule: H(X,Y) = H(X) + H(Y|X).
H(Y|X) <= H(Y): conditioning reduces entropy. Equality iff independent.
I(X;Y) = H(Y) - H(Y|X) = H(X)+H(Y)-H(X,Y) >= 0.

References

BookCover, T.M. and Thomas, J.A. Elements of Information Theory. 2nd ed. Wiley, 2006.