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

Because $X$ and $Y$ are independent random variables, conditioning on $Y$ merely translates $X$. The conditional entropy under a deterministic change of variables and the fact that conditioning reduces entropy therefore giveInterchanging $X$ and $Y$ similarly gives $H(X+Y)\ge H(Y)$, and henceThe proof applies to countable alphabets whenever the displayed information entropies are finite.

Write $p=(1+\mu {)}^{-1}$. Since $X$ and the geometric random variable $Z$ have the same expected value $\mu$,This is also the entropy deficit relative to the maximum entropy distribution on the nonnegative integers.

The random variables $X$ and $-Z$ are independent, so part a gives $H(X-Z)\ge H(-Z)=H(Z)$. Consequentlywhich is the required bound in terms of the Entropic Ruzsa distance.

Put $p_k=P_X(k)$. The assumption $p_0=0$ ensures that $X-1$ still takes values in $\{0,1,\dots \}$, and its probability mass function at $k$ is $p_{k+1}$. Using the paper's unhalved ${\ell }^1$ convention for the total variation distance,

Let $M={\max }_k{p}_k$ and choose an index $m$ with $p_m=M$. Splitting the overlap sum at $m$ givesso $1-q\ge M$. Moreover, information entropy dominates min-entropy gives $H(X)\ge -{\log }_{2}M$, and hence $2^{-H(X)}\le M\le 1-q$.

Apply Pinsker's inequality in natural logarithms. Because the paper writes total variation as the full ${\ell }^1$ distance, part c yieldsCombining the two estimates proves

The type of $x_1^n\in A^n$ is its empirical distributionIts type class isEvery string in $T(P)$ has $Q^n$-probabilitywhile the method of types gives $|T(P)|\le 2^{nH(P)}$. Therefore

The conditional probability mass function is

Conditionally on $X_1^n=x_1^n$, the uniform index $J$ selects the symbol $a$ with probability ${\hat{P}}_{x_1^n}(a)$. The law of total probability therefore givesThus $\overline{P}$ is the conditional mean type of a string in $B$.

Let $P_i$ be the marginal probability distribution of $X_i$. Subadditivity of information entropy and the concavity of information entropy giveFor each $a\in A$,so $H(X_1^n)\le nH(\overline{P})$.

Expand the logarithm of the product measure and exchange the finite sums:where part c identifies the expression in braces.

On $B$, part b gives ${\log }_2{P}_n={\log }_2{Q}^n-{\log }_2{Q}^n(B)$. Hence the information entropy of the conditional law satisfiesParts d and e implyExponentiation proves $Q^n(B)\le 2^{-nD(\overline{P}\Vert Q)}$.

For a binary prefix code with length function $L_n:A^n\to \mathbb{N}$, the Kraft inequality is

For the direct half of the code-distribution correspondence, let $L$ be the length function of a binary prefix code and putThen $R$ is a probability mass function andThus every prefix code determines a distribution whose ideal description lengths do not exceed the codeword lengths.

Conversely, given a probability mass function $R$, setfor $R(x)>0$. Then $2^{-L(x)}\le R(x)$, so the Kraft inequality is satisfied. Its converse supplies a binary prefix code with these lengths, andIf real lengths are allowed, the ideal choice $L(x)=-{\log }_{2}R(x)$ satisfies Kraft with equality.

Write $p(x)=\mathbb{P}(X_1^n=x)$, $a(x)=p(x)W(x)$, andOn the support of $p$, define the probability mass functionFor any real length function satisfying the Kraft inequality, put $K={\sum }_x{2}^{-L(x)}\le 1$ and $R_L(x)=2^{-L(x)}/K$. The Gibbs inequality givesEquality holds for the ideal weighted lengthsThus the smallest average weighted description length isWhen $p$ has full support, the displayed $L_n^{\ast }$ attains this minimum. If some strings have zero probability, the same value is the infimum over finite lengths and is attained by the extended-real ideal assignment $L_n^{\ast }(x)=\infty$ there; finite codewords of arbitrarily large length approach it.

Put $p_i=\mathbb{P}(X_i=1)$ and $\lambda ={\sum }_i{p}_i$. A relative-entropy form of the Poisson approximation bound for dependent Bernoulli variables isThe last two terms form the total correlation; they vanish when the Bernoulli variables are independent.

Here $D_e$ and $H_e$ use natural logarithms.

To prove the bound, let $Q_i$ be the Poisson distribution with mean $p_i$ and let $Q={⨂}_i{Q}_i$. Expanding the Kullback-Leibler divergence against this product law givesThe supplied one-dimensional estimate bounds the first sum by ${\sum }_i{p}_i^2$. Under the addition map, $P_{X_1^n}$ becomes $P_{S_n}$, while the sum of independent Poisson random variables under $Q$ has the Poisson distribution with mean $\lambda$. The data processing inequality for relative entropy proves the displayed result.

If a bound directly in the paper's unhalved total-variation norm is desired, Pinsker's inequality also gives

LetHere $S_n$ has the binomial distribution with parameters $(n,\lambda /n)$. Part a, now with independent coordinates, givesBy Pinsker's inequality, the probability mass functions therefore converge in total variation, and in particular $S_n$ converges in distribution to $Z\sim \mathrm{Poisson}(\lambda )$.

The joint probability of the observed row depends only on $S_n$:Taking logarithms in any fixed base and choosing $c_n=\log n$ giveswhereThe convergence lemma supplied in the question now yieldsThis sparse triangular array therefore has a random limiting normalized self-information rather than the constant limit in the usual asymptotic equipartition property.