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

The axioms for information entropy give the formula $H(X)=-{\sum }_{x}p(x)\log p(x)$ and hence the chain rule for information entropyBecause conditioning reduces entropy, $H(Y\mid X)\le H(Y)$, and thereforeThis is subadditivity of information entropy.

For the entropy submodularity rule, apply the chain rule for information entropy twice:The last quantity is conditional mutual information, whose nonnegativity again expresses that conditioning reduces entropy.

Solved by gpt-5.6-sol high.

Write $S_1=H(X)+H(Y)+H(Z)$ and $S_2=H(X,Y)+H(Y,Z)+H(Z,X)$. By the definition of mutual information,so the required right-hand side is $(2S_2-S_1)/3$.

Apply entropy submodularity to the pairs $(X,Y),(X,Z)$ and then cyclically permute the variables:Adding gives $2S_2\ge S_1+3H(X,Y,Z)$, which is exactly

Solved by gpt-5.6-sol high.

Because $X,Y,Z$ are independent random variables, adding $Y$ is an independent noise channel, sois a Markov chain. The data processing inequality for mutual information givesTranslation in the finite additive group preserves conditional entropy, and independence therefore givesandSubstitution proves the required entropy submodularity for three independent sums.

Solved by gpt-5.6-sol high.

For random variables $A,B$ in a finite additive group, take independent copies $A^{\prime },B^{\prime }$ with the same respective distributions and define the Entropic Ruzsa distance byFor the independent variables in the question, expansion givesPart iii, applied to the independent variables $X,Y,-Z$, saysSubtracting $H(X-Y)$ from both sides proves

Solved by gpt-5.6-sol high.