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.

Solution

Past exam of the mathematics course of the University of Cambridge / 2025 / iii / Paper 164 / 1 / i / Solution

 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2025/iii/paper-164/1/i/solution