Conditional Entropy

H(X | Y) measures how many bits of uncertainty survive after you see Y.

The idea

The conditional entropy $H(X \mid Y)$ measures the uncertainty that remains in $X$ after we observe a related variable $Y$.

Fix one observed value first. Given $Y = y$, the variable $X$ follows the conditional distribution $p(x \mid y)$, and that distribution has an ordinary entropy, written $H(X \mid Y = y)$. This number varies with $y$: some observations pin $X$ down and others barely narrow it. To measure how much $Y$ helps on average, weight each of these entropies by the probability of its observation:

$H(X \mid Y) = \sum_y \mathbb{P}(Y = y)\, H(X \mid Y = y).$

With base-$2$ logarithms inside, $H(X \mid Y)$ is measured in bits.

Note that $H(X \mid Y)$ is an average of entropies, not the entropy of an averaged distribution; the two are different numbers, and the definition takes the former.

The information diagram below places these quantities together. The circles represent the entropies $H(X)$ and $H(Y)$, and their overlap is the mutual information $I(X;Y)$ — the information the two variables share. The crescent of $H(X)$ outside the overlap is exactly $H(X \mid Y)$, the opposite crescent is $H(Y \mid X)$, and together the two circles span the joint entropy $H(X,Y)$.

Ways to work on it

• Walkthrough. Compute residual uncertainty from perfect observations, useless observations, and mutual information.
• Practice. Average the case-by-case uncertainties H(X | Y=y).
• Hardest. Find the uncertainty about X that survives an observation of Y.

Not sure where to start? Take the ten-question placement test.