Conditioning reduces entropy ($H(X\mid Y)\le H(X)$)

For finite discrete random variables $X,Y$, knowing $Y$ reduces the information entropy of $X$ on average: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.^[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.^[ref]

Consider a binary state $X$ and a report $Y$ with the following joint probability mass function:Before the report, $X=0$ is strongly favored: its information entropy is $H(X)=h_2(1/10)\approx 0.468996$ bits, where $h_2$ is binary entropy. A report $Y=1$ makes the two states equally likely, so $H(X\mid Y=1)=1$ bit, strictly larger than before. This report occurs with probability $1/5$. The more common report $Y=0$ determines $X=0$, giving $H(X\mid Y=0)=0$. Therefore the averaged conditional entropy isThe resulting mutual information is $I(X;Y)=h_2(1/10)-1/5\approx 0.268996$ bits. The rare report increases uncertainty about the state; that increase does not make the report useless. Together the reports remove uncertainty on average. These are stipulated probabilities in an exact model, not measured frequencies.

Let $X$ be a Bernoulli random variable with $\mathrm{Pr}(X=1)=p$. Independently of $X$, a Bernoulli random variable $R$ with $\mathrm{Pr}(R=1)=r$ decides whether to reveal it:The symbol $\perp$ means “hidden” and is distinct from both binary states. This is a binary erasure channel with erasure probability $1-r$. The hidden report leaves the posterior distribution equal to the prior distribution, because hiding is independent of the state. Either visible report determines $X$. Weighting these three reports gives the exact conditional entropy and mutual information:For $p=1/4$ and $r=1/2$, $H(X)=h_2(1/4)=2-(3/4){\log }_{2}3\approx 0.811278$ bits, while $H(X\mid Y)=I(X;Y)\approx 0.405639$ bits. With $r=0$ the report tells us nothing; with $r=1$ it reveals the state completely. If $0<p<1$, every positive reveal probability makes the conditioning inequality strict. At $p=0$ or $p=1$, the state was already known and every value of $r$ gives equality.

For a Bayesian inference problem, this model distinguishes an uninformative missing report from a decisive observed state. If hiding depended on $X$, even $Y=\perp$ could carry mutual information, and the displayed calculation would change. In lossless source coding, suppose both encoder and decoder already know the reveal pattern for repeated independent and identically distributed pairs. Only the hidden states require descriptions. Applying Shannon's source coding theorem to those states gives an asymptotic average rate $(1-r)h_2(p)$ bits per original state. A single hidden state need not have a codeword of that fractional length.

The reveal pattern itself has information entropy $H(R)=h_2(r)$. If that pattern must also be sent, the chain rule for information entropy gives $H(R,X)=h_2(r)+h_2(p)$, since $R$ and $X$ are independent random variables. Equivalently, $H(Y)=h_2(r)+r{h}_2(p)$ and $H(X,Y)=H(Y)+H(X\mid Y)=h_2(r)+h_2(p)$. Thus a saving in the description of $X$ given $Y$ assumes that $Y$ is already available; it is not a free saving in the description of the whole pair.

For finite discrete random variables $X,Y,Z$, retaining $Y$ and also observing $Z$ givesEquality means conditional independence of $X$ and $Z$ given $Y$. Both sides average over reports; the additional observation is retained alongside $Y$.^[ref]

A short proof of the original inequality uses Kullback-Leibler divergence: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.^[ref]

With appropriate probability density functions and finite differential entropies, $h(X)-h(X\mid Y)=I(X;Y)\ge 0$, with equality iff independence. Differential entropy does not reverse the inequality; infinite or undefined quantities cannot justify subtraction.^[ref]

However, differential entropy can be negative and depends on the choice of coordinates. For $X$ with a uniform distribution on an interval of length $a>0$, $h(X)={\log }_{2}a$; in particular $a=1/2$ gives $-1$. Rescaling $X$ by a constant $c>0$ adds ${\log }_{2}c$ to both $h(X)$ and $h(X\mid Y)$, whenever they are finite, leaving the mutual information unchanged.^[ref]

If a continuously distributed $X$ is revealed exactly, its conditional distribution is a Dirac measure with no ordinary probability density function. The discrete identity $H(X\mid X)=0$ has no finite differential entropy counterpart. Mutual information, defined through relative entropy, is infinite here.^[ref]