Skip to content
Tutorials Center
My learning

Topics

Lesson 6 of 37 ยท Entropy and Information

Joint and Conditional Entropy

Compute joint entropy H(X,Y) and conditional entropy H(Y|X) from a probability table, prove the chain rule numerically and see why conditioning never increases entropy.

Real data comes in pairs: a word and the word before it, a pixel and its neighbor, a sent bit and a received bit. To measure the uncertainty of pairs we extend entropy in two ways. Joint entropy H(X, Y) is the uncertainty of the pair. Conditional entropy H(Y | X) is the uncertainty that remains in Y once X is known.

These two ideas lead directly to the chain rule, the most useful identity in the subject, and set up mutual information.

Joint entropy

Treat the pair (X, Y) as one big variable with distribution p(x, y):

TEXT
H(X, Y) = - sum over x,y of p(x, y) log2 p(x, y)
Python Joint entropy of a table

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The pair carries fewer bits than the two variables taken separately, H(X, Y) < H(X) + H(Y), because they are dependent: part of what you learn from one is already implied by the other. When X and Y are independent the two sides are equal.

Conditional entropy

For a fixed value x, the conditional distribution p(y | x) has its own entropy H(Y | X = x). The conditional entropy averages these over x:

TEXT
H(Y | X) = sum over x of p(x) * H(Y | X = x)
         = - sum over x,y of p(x, y) log2 p(y | x)

It answers: "on average, how many bits do I still need to describe Y if the decoder already knows X?"

Python Conditional entropy two ways

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Both routes give the same number. Notice that sunny days leave you fairly sure there is no umbrella (low entropy), while rainy days leave you less sure; H(Y | X) averages the two, weighted by how often each occurs.

The chain rule

Because p(x, y) = p(x) p(y | x), taking -log2 and averaging gives

TEXT
H(X, Y) = H(X) + H(Y | X)

The uncertainty of a pair is the uncertainty of the first plus what is left of the second. For n variables it generalizes:

TEXT
H(X1, ..., Xn) = H(X1) + H(X2 | X1) + ... + H(Xn | X1, ..., X(n-1))

This is exactly how text compressors think: describe the first symbol, then the second given the first, and so on.

Python Check the chain rule

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The chain rule matches the direct definition to six decimals. Note that H(Y | X) and H(X | Y) are generally different: conditional entropy is not symmetric.

Conditioning never increases entropy

On average, knowing something cannot hurt:

TEXT
H(Y | X) <= H(Y)

with equality exactly when X and Y are independent. This is a statement about the average: a particular observation x may leave you more uncertain than before (a surprising answer can open new doubts), but averaged over all x, uncertainty cannot rise. The gap H(Y) - H(Y | X) is the mutual information, the subject of the next lesson.

Python Dependence lowers conditional entropy

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

At strength 0 the variables are independent and H(Y | X) = H(Y) = 1. At strength 1, Y equals X, so knowing X leaves zero uncertainty: H(Y | X) = 0.

If Y = f(X) for some function f, then H(Y | X) = 0. Conversely H(f(X)) <= H(X): processing data can only discard information. This is the seed of the data processing inequality in Properties and Inequalities.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does the chain rule state?

    The uncertainty of a pair is that of the first variable plus the remaining uncertainty of the second.
  2. 2. When do we have H(X, Y) = H(X) + H(Y)?

    Independence makes H(Y | X) = H(Y), so the chain rule collapses to a sum.
  3. 3. If Y is a deterministic function of X, then H(Y | X) is

    Once X is known, Y is fully determined, so no uncertainty remains.
  4. 4. Which statement is true in general?

    Conditioning reduces entropy on average. Conditional entropy is not symmetric and is never negative for discrete variables.

Summary

  • H(X, Y) is the entropy of the pair; H(Y | X) averages the entropy of the conditional distributions.
  • Chain rule: H(X, Y) = H(X) + H(Y | X), and it extends to any number of variables.
  • H(Y | X) <= H(Y), with equality iff independent; H(Y | X) = 0 if Y is a function of X.
  • Conditional entropy is not symmetric.

Next: Mutual Information