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

For nonnegative $a_i,b_i$, with $a={\sum }_i{a}_i$ and $b={\sum }_i{b}_i$, the log-sum inequality iswith the usual extended-value conventions. Equality holds when $a_i/b_i$ is constant wherever $a_i>0$.

Let $0\le \lambda \le 1$ and put $P=\lambda P_1+(1-\lambda )P_2$ and $Q=\lambda Q_1+(1-\lambda )Q_2$. For each alphabet symbol $x$, apply the log-sum inequality to $a_1=\lambda P_1(x)$, $a_2=(1-\lambda )P_2(x)$ and the corresponding $b$ values. Summing over $x$ giveswhich is joint convexity in $(P,Q)$.

For $Z={\mathbb{E}}_Q{e}^g$, define the exponentially tilted mass function $Q_g(x)=Q(x)e^{g(x)}/Z$. Gibbs inequality givesRearranging proves

The preceding inequality supplies the upper bound on the supremum. If $P$ has full support relative to $Q$, choose $g(x)=\log (P(x)/Q(x))$; then ${\mathbb{E}}_Q{e}^g=1$ and the objective equals $D_e(P\Vert Q)$. If $P(x)=0$ at some symbols, use this choice on the support of $P$ and put $g(x)=-M$ elsewhere. Letting $M\to \infty$ gives the same value. Finiteness of $D(P\Vert Q)$ guarantees that $Q$ is positive on the support of $P$. This proves the Gibbs variational principle for relative entropy.

Let $X_1,X_2,\dots$ be i.i.d. with mass function $Q$ on a finite alphabet, and let ${\hat{P}}_n$ be their empirical distribution. Sanov theorem states that for every set $\Gamma$ of probability mass functions,andwhere interior and closure use the probability-simplex topology. Thus the empirical distributions satisfy a large deviation principle with rate function $D_e(\cdot \Vert Q)$.

The likelihood-ratio event depends only on the type $R={\hat{P}}_n$ and isequivalently $D(R\Vert Q)\ge D(R\Vert P)$. This constraint defines a closed subset of the finite probability simplex, so Sanov's upper bound gives the exponentIt is strictly positive: the only distribution with zero divergence from $Q$ is $R=Q$, but $Q$ violates the constraint because $0=D(Q\Vert Q)<D(Q\Vert P)$. Compactness and continuity under full support keep the infimum away from zero. This exponent is the Chernoff information between $P$ and $Q$.

An error implies that some $\theta \ne {\theta }^{\ast }$ has likelihood at least that of ${\theta }^{\ast }$. A finite union bound and part (b) therefore givewhereEvery inner infimum is strictly positive by the argument in part (b), and the minimum of finitely many positive numbers is positive.

For feasible mass functions $Q_1,Q_2$ at distortion levels $d_1,d_2$, the mixture $Q=\lambda Q_1+(1-\lambda )Q_2$ has nonzero-symbol mass at most $\lambda d_1+(1-\lambda )d_2$. Concavity of information entropy givesTaking maximizing sequences proves

Regard the alphabet as the cyclic group $\mathbb{Z}/m\mathbb{Z}$ and put $E=X-Y$. For each $y$, subtraction by $y$ is a bijection, soBy concavity of $\varphi$, its monotonicity in the distortion allowance, and $\mathbb{E}{d}_Y=\mathbb{P}(X\ne Y)\le d$,Therefore

The previous part gives $R(d)\ge \log m-\varphi (d)$ for uniform $X$. To attain the bound, take $Y$ uniform on $\mathbb{Z}/m\mathbb{Z}$, choose an independent error $E$ whose mass function attains $\varphi (d)$, and set $X=Y+E$. Then $X$ is uniform, $\mathbb{P}(X\ne Y)=\mathbb{P}(E\ne 0)\le d$, andThus $I(X;Y)=\log m-\varphi (d)$ and equality holds. This is the rate-distortion function of a uniform source under Hamming distortion.

The direct codes-distributions correspondence says that every mass function $Q$ on a finite alphabet admits a binary prefix code with lengths $L(x)=\lceil -{\log }_{2}Q(x)\rceil$. Conversely, every binary prefix code has lengths satisfying the Kraft inequality $K={\sum }_x{2}^{-L(x)}\le 1$, and hence defines the mass function $Q_C(x)=2^{-L(x)}/K$.

For the distribution $Q_C$ from part (a),Thereforeby Gibbs inequality and $K\le 1$.

For any fixed threshold $R$, minimizing the excess-length probability means assigning the available strings shorter than $R$ to the most probable symbols. Repeating this exchange argument simultaneously for every threshold orders symbols by decreasing probability and assigns binary strings from shortest to longest. There are $2^{\ell }$ words of length $\ell$, so the $k$th word in shortlex order has lengthThis is the optimal one-to-one binary code.

For decreasing probabilities, the first $x$ symbols each have probability at least $P(x)$, so $xP(x)\le 1$. Hence

Relabeling an arbitrary alphabet in decreasing probability order makes part (ii) pointwise:It immediately impliesand, after taking expectations,This reverses the prefix-code lower bound from part (b). A general one-to-one code need not decode concatenated codewords instantaneously or uniquely, so it is not constrained by Kraft's inequality.