= Conditioning reduces entropy
{title2=$H(X\mid Y)\leq H(X)$}
For finite <discrete random variables> $X,Y$, knowing $Y$ reduces the <information entropy> of $X$ on average:
$$
H(X\mid Y)=\sum_{y:p_Y(y)>0}p_Y(y)H(X\mid Y=y)\leq H(X).
$$
Equality holds exactly when $X$ and $Y$ are <independent random variables>. The average over observations is essential: $H(X\mid Y=y)$ can exceed $H(X)$ for a particular $y$. All <logarithms> here have base two, giving <bits>, and zero-probability terms contribute zero.<6.441 Information Theory (Spring 2016 lecture notes) by Yury Polyanskiy and others/Chapter 1: Information Measures: Entropy and Divergence>[Definition 1.3, printed p. 8; Theorem 1.1(4), printed p. 10]{ref}
For <Bayesian inference>, this compares a <prior distribution> with the <posterior distributions> produced by possible observations. An unexpected report can make previously unlikely alternatives plausible, while useful reports reduce uncertainty overall. For <lossless source coding>, an observation shared by <encoder> and <decoder> lets them choose descriptions for the appropriate <conditional distribution>; sending that observation also has a cost. The example below makes both the saving and that cost explicit.
In <A Mathematical Theory of Communication by Claude Shannon> (1948), the definition of <conditional entropy> is already an average over observations, followed by the inequality and its <independence> condition in section 6, property 6. The phrase “knowledge reduces uncertainty” must be read with that averaging convention.<A Mathematical Theory of Communication by Claude Shannon>[p. 12; title page identifies C. E. Shannon and the 1948 journal publication]{ref}
Back to article page
