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.


1 Answer 1


Embarassingly, I found the answer in the lecture notes I was following (it was in a different section from the rest of the preliminary entropy results). The proof is also quite nice and a bit tricky, so for the sake of others Googling in future, I'll restate the proof here (with modifications in notation), which is attributed to Chris West.

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.

The general case follows from the continuity axiom and the fact that any discrete random variable can be approximated by discrete random variables with finite support and rational probabilities. ▮

  • $\begingroup$ 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$". $\endgroup$ Feb 2 at 4:56

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .