Past exam of the information theory course of the University of Oxford / 2023 / 2

The independent and identically distributed hypothesis factors the joint probability mass function:Symbols outside the support of a probability distribution $p$ never occur, almost surely. On its finite positive probability support, $\log p(X_i)$ is bounded, so the strong law of large numbers applies:This is the asymptotic equipartition property with the sign appropriate to a logarithm of a probability mass.

For a fixed estimated probability mass function $q$, the estimated joint probability mass function is $q_n(x_1,\dots ,x_n)={\prod }_{i}q(x_i)$. If $q(x)>0$ whenever $p(x)>0$, the strong law of large numbers gives the mismatched asymptotic equipartition property:Here $H(p,q)$ is cross-entropy, and the last equality is cross-entropy equals entropy plus relative entropy. The Kullback-Leibler divergence measures the extra average logarithmic loss from the estimated law.

If $q(x)=0$ for some $x$ with $p(x)>0$, let $a={\sum }_{x:q(x)=0}p(x)>0$. The probability that none of the first $n$ observations belongs to this set is $(1-a{)}^n\to 0$. Almost surely such a symbol eventually occurs, after which $q_n(X_1,\dots ,X_n)=0$ forever. Thus the limit is $-\infty$, consistent with infinite cross-entropy and infinite Kullback-Leibler divergence.

For every $x^n\in A^{n,\epsilon }$, the defining typical set constraint impliesLet $S_n=A^{n,\epsilon }\cap B^{n,\epsilon }$. Summing the lower probability mass bound over $S_n$ givesThereforeThe sample mean constraint can only shrink the typical set, so this cardinality upper bound holds for every positive integer $n$.

For fixed $\epsilon >0$, the asymptotic equipartition property gives $\mathrm{Pr}(X^n\notin A^{n,\epsilon })\to 0$. The strong law of large numbers applied to $X_i$, which are bounded because their numerical alphabet is finite, gives $\mathrm{Pr}(X^n\notin B^{n,\epsilon })\to 0$. The union bound therefore yieldsSince $\delta >0$, eventually $\mathrm{Pr}(X^n\in S_n)\ge 2^{-\delta }$. Each word in $S_n$ has probability mass at most $2^{-n(H(p)-\epsilon )}$, soRearranging provesfor sufficiently large $n$. The key is that the factor $2^{-\delta }$ is a fixed number below one, however small $\delta$ is. This is an instance of typical sets with an additional high-probability constraint.

First, the binary translation of a quaternary prefix code is still a prefix code: every translated codeword length is even, and a binary prefix relation would split into complete two-bit blocks, giving a prefix relation between the original quaternary codewords. Binary Huffman coding is optimal among binary prefix codes, soFor the other direction, let ${\ell }_i=|c_B(x_i)|$ and round these binary codeword lengths to quaternary lengths $k_i=\lceil {\ell }_i/2\rceil$. The Kraft inequality givesThe quaternary converse of the Kraft inequality supplies a quaternary prefix code with lengths $k_i$. Optimality of the quaternary Huffman code then impliesThus binary translation of an optimal quaternary code costs at most one extra bit per source symbol:The quaternary Huffman code uses the usual adjustment of adding zero-weight dummy leaves when needed. If the alphabet has one symbol, both optimal codes may use the empty codeword, giving the trivial endpoint.