# Conditioning reduces entropy, directly from Khintchine--Shannon axioms

Assume there is a function $${\bf H}\{X\}$$ on discrete random variables $$X$$ that satisfies the following axioms:

a) (Invariance.) If $$X$$ takes values in $$A$$, $$Y$$ takes values in $$B$$, $$\phi:A\to B$$ is a bijection, and $${\bf P}\{ Y = \phi(a)\} = {\bf P}\{X=a\}$$ for all $$a\in A$$, then $${\bf H}\{X\} = {\bf H}\{Y\}$$.

b) (Extensibility.) If $$X$$ takes values in $$A$$ and $$Y$$ takes values in $$B$$ for a set $$B$$ such that $$A\subseteq B$$, and furthermore $${\bf P}\{Y = a\} = {\bf P}\{X=a\}$$ for all $$a\in A$$, then $${\bf H}\{X\} = {\bf H}\{Y\}$$.

c) (Continuity.) The quantity $${\bf H}\{X\}$$ depends continuously on the probabilities $${\bf P}\{X=a\}$$.

d) (Maximisation.) Over all possible random variables $$X$$ taking values in a finite set $$A$$, the quantity $${\bf H}\{X\}$$ is maximised for the uniform distribution.

e) (Additivity.) For $$X$$ taking values in $$A$$ and $$Y$$ taking values in $$B$$, we have the formula $${\bf H}\{X,Y\} = {\bf H}\{Y\} + {\bf H}\{X | Y\},$$ where $${\bf H}\{X,Y\} = {\bf H}\{(X,Y)\}$$ and $${\bf H}\{X|Y\} = \sum_{y\in B} {\bf P} \{Y=y\} {\bf H}\{X| Y=y\}.$$

It can be shown that these five axioms determine the formula for entropy up to a multiplicative constant.

From these axioms alone (and without rederiving the formula for entropy), is it possible to prove that for all discrete random variables $$X$$ and $$Y$$, we have $${\bf H}\{X|Y\} \le {\bf H}\{X\} ?$$ This is used to show a useful submodularity inequality, but proof I've seen of this uses something like concavity of $$\log$$, or Jensen's inequality, but I wonder if there is a way to prove it sort of "symbolically" from the axioms.

Thanks in advance, and I apologise if this question has been asked before.

We shall show that $${\bf H}\{X|Y\} \le {\bf H}\{X\}$$.
Proof. Let $$A$$ be the support of $$X$$ and $$B$$ be the support of $$Y$$. First we consider the case that $$X$$ is uniform on $$A$$ (so $$A$$ is finite). Then by the definition of conditional entropy, $${\bf H}\{X| Y\} = \sum_{b\in B} {\bf P}\{Y = b\} {\bf H}\{X |Y= b\}.$$ But for each $$b$$, the random variable $$(X| Y = b)$$ takes values in $$A$$, so its entropy is bounded above by $${\bf H}\{X\}$$ by the maximisation axiom. Hence $${\bf H}\{X| Y\} \le {\bf H}\{X\}$$.
Next, suppose that $$A$$ and $$B$$ are both finite and suppose further that $${\bf P}\{Y = b\}$$ is rational for all $$b$$. Then there is an integer $$n$$ and integers $$\{m_b\}_{b\in B}$$ such that $${\bf P}\{Y= b\} = m_b/n$$ for all $$b\in B$$. Now partition $$[n]$$ into sets $$\{E_b\}_{b\in B}$$, where $$|E_b| = m_b$$ for all $$b\in B$$. We define a random variable $$Z$$ by sampling uniformly at random from $$E_b$$ if $$Y = b$$, and doing so independently of $$(X| Y=b)$$. The result is a random variable $$Z$$ that is uniform on $$[n]$$ and which is independent of $$X|Y$$. Furthermore, since $$Z$$ determines $$Y$$, we have $${\bf H}\{Z\} = {\bf H}\{Y,Z\}$$ by the invariance axiom. Hence \begin{align} {\bf H}\{X| Y\} &= {\bf H}\{X| Y, Z\} \cr &= {\bf H}\{X,Y,Z\} - {\bf H}\{Y,Z\} \cr &= {\bf H}\{X,Z\} - {\bf H}\{Z\} \cr &= {\bf H}\{X|Z\} \cr &\le {\bf H}\{X\},\cr \end{align} where the last line follows from the previous paragraph.
• Nice, thanks for posting this answer. A detail: it doesn't make sense to say "the random variable $(X\mid Y=b)$". Instead one should say "a random variable whose distribution is the conditional distribution of $X$ given $Y=b$". Feb 2 at 4:56