= Additional conditioning reduces entropy
{title2=$H(X\mid Y,Z)\leq H(X\mid Y)$}
For finite <discrete random variables> $X,Y,Z$, retaining $Y$ and also observing $Z$ gives
$$
H(X\mid Y)-H(X\mid Y,Z)=I(X;Z\mid Y)\geq0.
$$
Equality means <conditional independence> of $X$ and $Z$ given $Y$. Both sides average over reports; the additional observation is retained alongside $Y$.<6.441 Information Theory (Spring 2016 lecture notes) by Yury Polyanskiy and others/Chapter 2: Information Measures: Mutual Information>[Definition 2.4 and Theorem 2.5(1), printed pp. 26–27]{ref}
A short proof of the original inequality uses <Kullback-Leibler divergence>:
$$
H(X)-H(X\mid Y)=I(X;Y)=\sum_{y:p_Y(y)>0}p_Y(y)D(p_{X\mid Y=y}\Vert p_X)\geq0.
$$
<Gibbs inequality> makes each term nonnegative, vanishing exactly when $p_{X\mid Y=y}=p_X$: <independence> for every possible report. Applying this within each $Y=y$ and averaging proves the additional-conditioning inequality.<6.441 Information Theory (Spring 2016 lecture notes) by Yury Polyanskiy and others/Chapter 2: Information Measures: Mutual Information>[Theorem 2.1, printed p. 20; Theorem 2.3(1,3), printed p. 23; Theorem 2.4(2) and Corollary 2.4, printed p. 24]{ref}
Back to article page
