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

Stein's lemma states that for testing $P^{\otimes n}$ against $Q^{\otimes n}$, the smallest Type II error ${\beta }_n$ among tests with Type I error at most any fixed $0<\epsilon <1$ satisfies

The Neyman-Pearson lemma gives an optimal acceptance region for $P$ of the formwith possible boundary randomization. If ${\hat{P}}_n$ is the empirical mass function, thenso equivalently

Fix $\delta >0$ and chooseUnder $P$, the weak law of large numbers makes the normalized log likelihood ratio converge in probability to $D(P\Vert Q)$, so $P^{\otimes n}(B_n({\tau }_n))\to 1$. On this Neyman-Pearson decision region,and henceLetting $\delta \downarrow 0$ proves the direct bound.

For any region $B_n$ with $P^{\otimes n}(B_n)\ge 1-\epsilon$, letThe weak law of large numbers gives $P^{\otimes n}(C_n)\to 1$, so $P^{\otimes n}(B_n\cap C_n)\ge 1-\epsilon -o(1)$. ThereforeThus $\mathrm{limsup}-n^{-1}\log {\beta }_n\le D(P\Vert Q)+\delta$; let $\delta \downarrow 0$.

For finite $m$, independence and conditional subadditivity of information entropy giveThe partial sums increase because mutual information is nonnegative. Taking $m\to \infty$ proves $H(Z)\ge {\sum }_{i\ge 1}I(X_i;Z)$.

For $S_i=[n]\setminus \{i\}$, the chain rule for information entropy givesEach summand is at least $H(X_j\mid X_1^{j-1})$ because conditioning reduces entropy. Summing over $i$, each $j$ occurs $n-1$ times:This is the required special case of Shearer's inequality.

Writing $Q_j$ for the $j$th marginal and using $P={\prod }_j{P}_j$,The analogous formula for $D(Q^{(i)}\Vert P^{(i)})$ omits coordinate $i$. ConsequentlyPart b makes ${\sum }_{i}H(Q^{(i)})\ge (n-1)H(Q)$, so the last display is at least $D(Q\Vert P)$.

The three-point identity for relative entropy isIt follows by expanding and collecting logarithms. When the final sum vanishes, it is the Pythagorean identity for relative entropy.

For $Q_t=(1-t)Q^{\ast }+t{Q}^0$, convexity gives $Q_t\in E$. Minimality at $t=0$ impliesSince $P$ has full support and the minimum is finite, $Q^{\ast }$ has full support.

For $A^{\prime }=\{a:P^{\prime }(a)>0\}$,using nonnegativity and part i.

Expanding the three divergences givesThe inequality $\log u\ge 1-u^{-1}$ bounds this below by the nonnegative expression in part ii. Hence

The binary Kraft inequality states that codeword lengths $l(a)$ of a prefix code, or more generally a uniquely decodable code, satisfyConversely, positive integer lengths obeying this inequality can be realized by a binary prefix code.

The Shannon lengths are $l_S(a)=\lceil {\log }_2(1/P(a))\rceil$. Their Competitive optimality of the Shannon code says that for every binary uniquely decodable code of lengths $l_C$ and every positive integer $k$,On this event, $P(X)<2^{-l_C(X)-k+1}$. Summing and applying the Kraft inequality proves

Relabel the symbols so $p_1\ge \cdots \ge p_m$ and assign all finite binary strings in nondecreasing length order, beginning with the empty string. The $i$th string has lengthSince $1\ge {\sum }_{j=1}^i{p}_j\ge i{p}_i$,Thus the optimal one-to-one binary code satisfies

For the uniform distribution, the code in part c hasbecause every summand is at most ${\log }_{2}m$ and at least one is strictly smaller. For $m=3$, the explicit code $C(1)=\lambda$, $C(2)=0$, $C(3)=1$ has mean length $2/3<{\log }_{2}3$.