Past exam of the mathematics course of the University of Cambridge / 2026 / iii / Paper 224 (Information Theory)

Suppose $X\to Y\to Z$ is a Markov chain, so $I(X;Z\mid Y)=0$. The chain rule for mutual information givesand alsobecause conditional mutual information is nonnegative. Therefore $I(X;Z)\le I(X;Y)$. Similarly,while $I(X,Y;Z)=I(X;Z)+I(Y;Z\mid X)\ge I(X;Z)$, so $I(X;Z)\le I(Y;Z)$. These are the two data processing inequalities. In particular, applying any deterministic function or Markov kernel to either argument cannot increase mutual information.

Solved by gpt-5.6-sol high.

Independence makesa Markov chain. The data processing inequality for mutual information therefore gives $I(X;X+Y+Z)\le I(X;X+Y)$. Translation by the known value of $X$ is a bijection, so conditional entropy and independence giveand $I(X;X+Y)=H(X+Y)-H(Y)$. Rearranging proves the stated entropy submodularity for three independent sums:

Solved by gpt-5.6-sol high.

Because the Entropic Ruzsa distance depends only on marginal distributions, take $X,Y,Z$ independent with the required marginals. Since $X-Z=(X-Y)+(Y-Z)$ is a function of $(X-Y,Y-Z)$, the data processing inequality for mutual information yieldsThe map $(X,X-Y,Y-Z)\mapsto (X,Y,Z)$ is a bijection. Using independence and the chain rule for information entropy, the left side iswhereas the right side is $H(X-Z)-H(Z)$. Hencewhere the final step is subadditivity of information entropy. Substituting this inequality into the definition of $d_R$ gives the Entropic Ruzsa triangle inequality

Solved by gpt-5.6-sol high.

Let $X_1,X_2,Y$ be independent, with $X_1,X_2$ distributed as $X$. Apply part (b) to $X_1,-Y,X_2$:Adding an independent random variable cannot decrease information entropy, soIn terms of Entropic Ruzsa distance, this is $d_R(X,-X)\le 2d_R(X,Y)$. The Entropic Ruzsa triangle inequality and invariance under simultaneous negation now givewhich is the Entropic Ruzsa sum-difference inequality.

Solved by gpt-5.6-sol high.

For independent $X,Y$, expand the Entropic Ruzsa sum-difference inequality from part (d):Collecting the information entropy terms givesReplacing $Y$ by $-Y$ interchanges sum and difference and preserves $H(Y)$, yielding the requested orientation

Solved by gpt-5.6-sol high.

Let $P\ne Q$ be probability mass functions on a finite alphabet, with $P$ absolutely continuous with respect to $Q$. A decision region $B_n$ accepts the null law $P^{\otimes n}$. Writefor its type-I and type-II errors. Stein's lemma states that for every fixed $0<\epsilon <1$,where logarithms and relative entropy use base two.

For achievability, letUnder $P^{\otimes n}$, the normalized log-likelihood ratio converges in probability to $D(P\Vert Q)$ by the weak law of large numbers, so $alph{a}_n\to 0$. On $B_n$, $Q^{\otimes n}\le 2^{-n(D(P\Vert Q)-\eta )}{P}^{\otimes n}$, whence ${\beta }_n\le 2^{-n(D(P\Vert Q)-\eta )}$.

For the converse, letAgain $P^{\otimes n}(A_n)\to 1$. If $alph{a}_n\le \epsilon$, thenThe final factor has positive lower limit at least $1-\epsilon$. Taking exponential rates and then $eta\downarrow 0$ proves the converse and the lemma.

Solved by gpt-5.6-sol high.

The Neyman-Pearson decision region accepting $P^{\otimes n}$ iswith randomization on the boundary when needed. If $R={\hat{P}}_{x_1^n}$ is the type of the observed string, thenThus the equivalent relative entropy form is

Solved by gpt-5.6-sol high.

LetThe minimum exists because the probability simplex is compact. Let $R^{\ast }$ be the information projection of $Q$ onto the closed convex set ${\mathcal{C}}_{\delta }$. Its Pythagorean inequality says that every $R\in {\mathcal{C}}_{\delta }$ satisfiesFor a string $x_1^n$ of type $R\in {\mathcal{C}}_{\delta }$, this givesSumming over the decision region $B_n$ proves the exact bound

Solved by gpt-5.6-sol high.

Here $e_2^{(n)}=P^{\otimes n}(B_n^c)$. The method of types gives at most $(n+1{)}^{|A|}$ possible values of type, and a type class $T_R$ hasEvery type in $B_n^c$ has $D(R\Vert P)>\delta$, soThe polynomial prefactor has zero exponential rate. Therefore

Solved by gpt-5.6-sol high.

For nonnegative numbers $a_i,b_i$, put $a={\sum }_i{a}_i$ and $b={\sum }_i{b}_i$. The log-sum inequality iswith $0\log (0/b)=0$ and the usual extended-value convention when a denominator vanishes. Equality holds precisely when $a_i/b_i$ is constant over the indices with $a_i>0$.

Solved by gpt-5.6-sol high.

Let $K(y\mid x)$ be a Markov kernel, and let $P_Y=PK$, $Q_Y=QK$ be the output probability distributions. Applying the log-sum inequality for each $y$ to $a_x=P(x)K(y\mid x)$ and $b_x=Q(x)K(y\mid x)$ givesSumming over $y$ and using ${\sum }_{y}K(y\mid x)=1$ yields the data processing inequality for relative entropy

Solved by gpt-5.6-sol high.

The elementary logarithm inequality ${\log }_{2}u\le ({\log }_{2}e)(u-1)$ givesSince ${\sum }_x(P(x)-Q(x))=0$,This proves $D(P\Vert Q)\le (\log e){\chi }^2(P\Vert Q)$, relating relative entropy to chi-squared divergence.

Solved by gpt-5.6-sol high.

Writing $P,Q$ for the laws of $X,Y$, respectively, and using Jensen inequality for the concave natural logarithm,This is the lower-bound half of the Gibbs variational principle for relative entropy.

Solved by gpt-5.6-sol high.

Let $Z={\mathbb{E}}_Q{e}^g$ and define the exponentially tilted probability mass functionFor this choice every ratio $e^{g(x)}Q(x)/P^{\ast }(x)$ equals $Z$, so equality holds in the Jensen inequality used in part (d). Henceand $P^{\ast }$ is the maximizer. This is the finite-alphabet Gibbs variational principle for relative entropy.

Solved by gpt-5.6-sol high.

For $\mu >0$, let $Q$ be the geometric distributionIf $P$ is the law of $X$, Gibbs inequality givesThereforeFor $\mu =0$, the nonnegative random variable $X$ is zero almost surely and both sides vanish. This proves that the maximum entropy distribution on the nonnegative integers with fixed expected value is geometric.

Solved by gpt-5.6-sol high.

Order the symbols so that $p_1\ge p_2\ge \cdots$. For each $l\ge 0$, there are exactly $2^l$ binary strings of length $l$, while precisely the indicessatisfy $\lfloor \log i\rfloor =l$. Assign those $2^l$ symbols bijectively to the strings of length $l$. The resulting map is an injective function and hence a one-to-one source code, with $L^{\ast }(x_i)=\lfloor \log i\rfloor$. Assigning shorter available words to more probable symbols also shows that this is an optimal one-to-one binary code.

Solved by gpt-5.6-sol high.

Monotonicity of the ordered probabilities gives $i{p}_i\le {\sum }_{j\le i}{p}_j\le 1$, so $\log i\le -\log p_i$. ConsequentlyGiven $L^{\ast }(X)=l$, the source symbol can take at most $2^l$ values. The maximum entropy distribution on a finite set is uniform, henceAveraging this conditional entropy inequality proves

Solved by gpt-5.6-sol high.

Put $L=L^{\ast }(X)$ and $\mu =\mathbb{E}L$. Since $L$ is a function of $X$, the chain rule for information entropy and part (c) givePart (a), applied to the nonnegative integer-valued random variable $L$, yieldsThe logarithm inequality $\log (1+t)\le t\log e$ implies $\mu \log (1+1/\mu )\le \log e$. ThusPart (c) also gives $\mu \le H(X)$, so monotonicity of the logarithm lets us replace $\log (1+\mu )$ by $\log (H(X)+1)$. Rearranging proves

Solved by gpt-5.6-sol high.