Conditional Entropy

Definition

The Conditional Entropy $H(X|Y)$ quantifies the average uncertainty remaining about $X$ after $Y$ has been observed. It is defined as the expected value of the conditional information content:

$$H(X|Y)=\mathbb{E}\left[{\log }_2\frac{1}{p(X|Y)}\right]=\sum _{x,y}p(x,y){\log }_2\frac{1}{p(x|y)}[\text{bits}]$$

Alternatively, $H(X|Y)$ is the weighted average of the entropies of $X$ conditioned on each possible value of $Y$:

$$H(X|Y)=\sum _{y\in {\mathcal{A}}_Y}p(y)H(X|Y=y)$$

This result confirms that the conditional entropy is the expected value of the entropy of the conditional distribution $p(x|y)$, averaged over all possible values of $Y$.

Proof 1: Algebraic Expansion

By expanding the joint probability $p(x,y)=p(y)p(x|y)$, the definition is rewritten as:

$$\begin{array}{rl}H(X|Y)& =\sum _{y\in {\mathcal{A}}_Y}\sum _{x\in {\mathcal{A}}_X}p(y)p(x|y){\log }_2\frac{1}{p(x|y)}\\ & =\sum _{y\in {\mathcal{A}}_Y}p(y)\underset{H(X|Y=y)}{\underbrace{\left[\sum _{x\in {\mathcal{A}}_X}p(x|y){\log }_2\frac{1}{p(x|y)}\right]}}\\ & =\sum _{y\in {\mathcal{A}}_Y}p(y)H(X|Y=y)\end{array}$$

Proof 2: Law of Iterated Expectations

A more concise proof utilizes the property that for any function $g(X,Y)$, the global expectation is the expectation of the conditional expectations, $E[g(X,Y)]=E_Y[E_X[g(X,Y)|Y]]$.

Let $g(X,Y)={\log }_2\frac{1}{p(X|Y)}$. Then:

$$\begin{array}{rl}H(X|Y)& =\mathbb{E}\left[g(X,Y)\right]\\ & ={\mathbb{E}}_Y\left[{\mathbb{E}}_X\left[{\log }_2\frac{1}{p(X|Y)}|Y\right]\right]\end{array}$$

For a fixed $Y=y$, the inner expectation represents the entropy of the conditional distribution $p(x|y)$:

$${\mathbb{E}}_X\left[{\log }_2\frac{1}{p(X|y)}|Y=y\right]=H(X|Y=y)$$

Substituting this back into the outer expectation yields:

$$H(X|Y)={\mathbb{E}}_Y\left[H(X|Y=y)\right]=\sum _{y\in {\mathcal{A}}_Y}p(y)H(X|Y=y)$$