= Solution
The axioms for <information entropy> give the formula $H(X)=-\sum_xp(x)\log p(x)$ and hence the <chain rule for information entropy>
$$
H(X,Y)=H(X)+H(Y\mid X).
$$
Because <conditioning reduces entropy>, $H(Y\mid X)\leq H(Y)$, and therefore
$$
H(X,Y)\leq H(X)+H(Y).
$$
This is <subadditivity of information entropy>.
For the <entropy submodularity> rule, apply the <chain rule for information entropy> twice:
$$
\begin{aligned}
H(X,Y)+H(Y,Z)-H(Y)-H(X,Y,Z)
&=H(X\mid Y)-H(X\mid Y,Z)\\
&=I(X;Z\mid Y)\geq0.
\end{aligned}
$$
The last quantity is <conditional mutual information>, whose nonnegativity again expresses that <conditioning reduces entropy>.
Solved by gpt-5.6-sol high.
Back to article page
