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

Stein's lemma states that for distinct probability mass functions $P,Q$ on a finite alphabet, the best exponential decay rate of the Type II error ${\beta }_n=Q^{\otimes n}(B_n)$ among tests whose Type I error ${\alpha }_n=P^{\otimes n}(B_n^c)$ is eventually at most any fixed $ϵ\in (0,1)$ is

For the direct part, define the information-density typical regionThe weak law of large numbers under $P$ gives ${\alpha }_n\to 0$, while

For the converse, letAgain $P^{\otimes n}(C_n)\to 1$. Any test with $P^{\otimes n}(B_n)\ge 1-ϵ$ satisfiesOn $C_n$, $Q^{\otimes n}\ge 2^{-n(D+\delta )}{P}^{\otimes n}$, henceThus ${\mathrm{limsup}}_n-n^{-1}{\log }_2{\beta }_n\le D+\delta$. Letting $\delta \downarrow 0$ proves optimality.

Using the paper's full-${\ell }^1$ convention, the total variation distance isLet $A_{+}=\{a:P(a)\ge Q(a)\}$. Since the signed differences sum to zero,For every $B\subseteq A$, its positive difference is at most the sum over $A_{+}$, and its negative difference has the same bound by taking the complement. Therefore

Let $B_n$ be the region on which the test chooses $P_n$. ThenMinimizing over decision regions is therefore equivalent to maximizing the signed difference. Part b givesThe minimizing region is $\{x:P_n(x)\ge Q_n(x)\}$, the equal-prior Neyman-Pearson decision region.

For an independent identically distributed source with mass function $P$ on a finite alphabet and a fixed compression rate $R>H(P)$, the optimal probability of decoding error has exponentmeaning that the best fixed-rate codes satisfyat continuity points of the exponent.

For the direct part, let $m=|A|$ andEncode every sequence whose type $Q$ satisfies $H(Q)\le R-{\eta }_n$. The method of types bounds the number of such sequences byso they fit into a rate-$R$ codebook. The error probability obeysCompactness of the probability simplex and continuity of entropy and relative entropy on the support of $P$ givewhich is the direct bound.

The test accepts $P$ when $D({\hat{P}}_n\Vert P)\le \delta$. Under $P$, the method of types givessoUnder $Q$, accepting $P$ requires a type in the closed set $\{R:D(R\Vert P)\le \delta \}$. ThereforewhereConsequently ${\mathrm{limsup}}_n{n}^{-1}{\log }_2{e}_i^{(n)}\le -D_i(\delta )$ for $i=1,2$. The first exponent is positive when $\delta >0$. Because relative entropy vanishes only when its arguments agree, the second is positive exactly while $Q$ lies outside the constraint set. Thus both are strictly positive for

The type of $x_1^n\in A^n$ is its empirical mass functionFor a product source $Q^{\otimes n}$,with the usual convention that the probability is zero if the string uses a symbol outside the support of $Q$.

The type class isWe first prove a multinomial-mode lemma. If $K=(K_a{)}_{a\in A}$ has the multinomial law with parameters $n$ and an $n$-type $P$, then $K=nP$ is a mode. Indeed, if $k_a<nP(a)$ and $k_b>nP(b)$, moving one count from $b$ to $a$ changes the probability by the factorRepeated transfers reach $nP$ without decreasing probability. There are at most $(n+1{)}^m$ count vectors, so the modal vector has probability at least $(n+1{)}^{-m}$.

Every string in $T(P)$ has $P^{\otimes n}$-probabilityThe lemma therefore givesand hence

Draw $X_1^n$ uniformly from $B$ and let $J$ be uniform on $\{1,\dots ,n\}$ independently. ThenIf $P_i$ denotes the marginal law of $X_i$, this also says $P_B=n^{-1}{\sum }_i{P}_i$. Since $X_1^n$ is uniform on $B$,Subadditivity of information entropy followed by concavity of information entropy givesExponentiating proves $|B|\le 2^{nH(P_B)}$.

The binary Kraft inequality says that codeword lengths $l_1,l_2,\dots$ of a prefix code satisfyConversely, suppose positive integer lengths obey this inequality and arrange them in nondecreasing order. Construct codewords greedily in the infinite binary tree. Before assigning length $l_i$, each earlier codeword of length $l_j\le l_i$ excludes exactly $2^{l_i-l_j}$ nodes at depth $l_i$. Thus the number excluded iswhere strictness follows because the remaining term $2^{-l_i}$ occurs in the full Kraft sum. A free depth-$l_i$ node therefore exists. Assign it as the next codeword; choosing a node not below an earlier codeword preserves prefix-freeness. Induction constructs the required prefix code.

Write $p_k=\mathbb{P}(X=k)$. Monotonicity givesso $p_k\le 1/k$ and therefore ${\log }_{2}k\le {\log }_2(1/p_k)$ whenever $p_k>0$. Hence

A distribution on $\{1,2,\dots \}$ must have $\mu \ge 1$. For $\mu >1$, put $p=1/\mu$ and letFor any mass function $P$ with mean $\mu$, Gibbs inequality givesThus the geometric distribution uniquely maximizes entropy. For $\mu =1$, the only admissible law is the point mass at one, which is the limiting geometric case $p=1$.

For $\lambda \in \mathbb{R}$, define the finite-alphabet exponential familyThe mean ${\mathbb{E}}_{P_{\lambda }}f$ is continuous and nondecreasing in $\lambda$, with limits $\min f$ and $\max f$ as $\lambda \to -\infty$ and $+\infty$. The strict interior assumption on $v$ therefore supplies a $\lambda$ with ${\mathbb{E}}_{P_{\lambda }}f=v$.

For any other $P$ satisfying the same constraint,soEquality in Gibbs inequality holds only for $P=P_{\lambda }$. Hence this Gibbs-form mass function is the unique entropy maximizer.