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

If $X\to Y\to Z$ is a Markov chain, the two forms of the data processing inequality for mutual information areThe chain rule for mutual information and the Markov property $I(X;Z\mid Y)=0$ giveUsing the other order,because conditional mutual information is nonnegative. This proves the first inequality. Applying the same result to the reversed Markov chain $Z\to Y\to X$, which has the same conditional-independence statement, proves the second.

Let $V,V^{\prime },U$ be mutually independent, with $V,V^{\prime }$ identically distributed. Entropy submodularity for three independent sums givesIndependent addition cannot decrease discrete entropy, because $H(V+V^{\prime }+U)\ge H(V+V^{\prime }+U\mid U)=H(V+V^{\prime })$. Hence

Take $U$ to have the distribution of $-X$ and take $V,V^{\prime }$ to be independent copies of $X$, all mutually independent. Then $U+V$ and $U+V^{\prime }$ both have the distribution of $X-Y$, whereas $V+V^{\prime }$ has the distribution of $X+Y$ and $H(U)=H(X)$. HenceorThe denominator is nonnegative because conditioning on $Y$ recovers $X$ from $X-Y$, so $H(X-Y)\ge H(X-Y\mid Y)=H(X)$.

Stationarity gives $H(X_n)=H(X_{n+1})=H(X_1)$. The Markov relation $X_1\to X_n\to X_{n+1}$ and the data processing inequality for mutual information implyUsing $H(X_n\mid X_1)=H(X_n)-I(X_1;X_n)$ on both sides gives

The Markov property gives $I(X_1;X_4\mid X_3)=I(X_2;X_4\mid X_3)=0$. The chain rule therefore yieldsandConditional on $X_4$, the factorization of the chain still gives $X_1\to X_2\to X_3$. The conditional data-processing inequality thus givesRearranging proves

Let $S(\alpha )={\sum }_{y}Q(y{)}^{\alpha }$. Both $\log S(\alpha )$ and $1-\alpha$ vanish at one. By L'Hopital rule, with logarithms to base two,Terms with $Q(y)=0$ contribute zero by continuity.

The code-distribution correspondence starts from the Kraft inequality. For codeword lengths $L(x)$ putConversely, a probability mass function determines ideal lengths $-{\log }_{2}R(x)$, up to integer rounding. For the source law $P_n$,using nonnegativity of Kullback-Leibler divergence and $K\le 1$.

Use the distribution $R$ associated with the code in part b. Since $2^{L(x)}=(KR(x){)}^{-1}$,For $\alpha =1/(1+\rho )$, Holder inequality, equivalently the indicated Jensen inequality, givesTherefore

Let $\rho \downarrow 0$, so $\alpha =1/(1+\rho )\to 1$. For the finite code alphabet,by differentiating the logarithmic moment-generating function at zero. Part a gives $H_{\alpha }(X_1^n)\to H(X_1^n)$, so the inequality in part c converges to $\mathbb{E}L\ge H(X_1^n)$.

Let $X_1,\dots ,X_n$ be IID with full-support mass function $Q$ on a finite alphabet $\mathcal{A}$, and let the empirical distribution beSuppose $E$ is a set of probability mass functions satisfying $E=\overline{E^{\circ }}$ and that the information projection $P^{\ast }$ minimizes $D(P\Vert Q)$ over $E$. Then the limiting Sanov theorem is

For each $n$-type $P$, the method of types givesand there are at most $(n+1{)}^{|\mathcal{A}|}$ types. Summing the upper bounds over types in $E$ gives the large-deviation upper bound. For the lower bound, choose types $P_n\in E$ converging to an interior distribution arbitrarily close to $P^{\ast }$ and use the lower type-class bound. Polynomial factors disappear after applying $-n^{-1}{\log }_2$, and continuity of divergence finishes the proof.

Define the closed setIt does not contain $Q$. Since the probability simplex is compact, $Q$ has full support, and Kullback-Leibler divergence is continuous and vanishes only at $Q$,The event in the question is exactly $\{{\hat{P}}_n\in E_{ϵ}\}$. The upper-bound half of Sanov theorem gives probability at most a polynomial factor times $2^{-n{c}_{ϵ}}$, which tends to zero. This proves the weak law of large numbers.

For an IID finite-alphabet source $Q$ and a fixed rate $H(Q)<R<{\log }_2|\mathcal{A}|$, let $P_e^{\ast }(n,R)$ be the smallest probability that a block is not represented by a fixed-to-fixed code having at most $2^{nR}$ codewords. The fixed-rate source-coding error exponent theorem states

For the direct part, encode all type classes whose empirical entropy is at most $R-{\delta }_n$, where ${\delta }_n\downarrow 0$ and $n{\delta }_n-|\mathcal{A}|{\log }_2(n+1)\to \infty$. Since a type class has at most $2^{nH(P)}$ sequences and there are at most $(n+1{)}^{|\mathcal{A}|}$ types, this codebook has at most $2^{nR}$ entries for large $n$. An error can occur only when $H({\hat{P}}_n)>R-{\delta }_n$. The method of types bounds its probability byTaking the lower limit of the exponent and using compactness and continuity gives at least $D^{\ast }(R,Q)$, proving achievability.

Let $Z(\alpha )={\sum }_{x}Q(x{)}^{\alpha }$ and $\ell (x)={\log }_{2}Q(x)$. ThenDifferentiation of this exponential family givesThe first-order terms cancel, leaving

Part b shows that $H(Q_{\alpha })$ decreases continuously from $H(Q_0)={\log }_2|\mathcal{A}|$ to $H(Q_1)=H(Q)$. Because $Q$ is nonuniform, the variance in part b is positive, so for each intermediate $R$ there is a unique ${\alpha }^{\ast }\in (0,1)$ with $H(Q_{{\alpha }^{\ast }})=R$.

To minimize $D(P\Vert Q)$ subject to $H(P)\ge R$, the optimum lies on the boundary $H(P)=R$. The Lagrange multiplier equations forgive $P(x)\propto Q(x{)}^{\alpha }$ for some $\alpha \in (0,1)$. The entropy constraint selects $\alpha ={\alpha }^{\ast }$ uniquely. Therefore