Past exam of the information theory course of the University of Oxford / 2021 (A16551W1, B8.4)

Source paper: released examination archive.

All logarithms have base two. In part a the information entropy differences and information expressions are interpreted where they are well defined; finite joint entropy is a sufficient hypothesis. This avoids undefined expressions such as infinity minus infinity.

The chain rule for conditional entropy givesIndeed, for every conditioning value $(x,z)$ of positive probability, each summand $-p(y\mid x,z){\log }_{2}p(y\mid x,z)$ is nonnegative. Its sum is zero exactly when the conditional probability mass function is concentrated at one value. Averaging over $(X,Z)$ therefore proves both the inequality and its equality criterion: equality holds exactly when $Y=f(X,Z)$ almost surely for some function $f$. Conditioning values of probability zero impose no restriction. This is a statement about discrete random variables; a differential entropy need not be nonnegative.

Expand the two observations in order using the chain rule for mutual information:The remaining conditional mutual information isRelative entropy nonnegativity proves the inequality. Equality requires every positive-weight relative entropy to vanish, which is equivalent to $p(y,z\mid x)=p(y\mid x)p(z\mid x)$ for every $x$ of positive probability. Thus equality holds exactly when $Y$ and $Z$ have conditional independence given $X$. No unconditional independence is required.

The chain rule for information entropy converts the two differences into conditional entropies. Their gap, in the order right minus left, isThis is additional conditioning reduces entropy. The relative entropy representation of conditional mutual information identifies exactly when that gap vanishes: equality holds if and only if $Y$ and $Z$ have conditional independence given $X$. Knowledge of $Y$ then changes no conditional probability of $Z$ after $X$ is known.

Here the asserted bound is actually an identity, so equality always holds whenever the displayed quantities are defined. Expand the same mutual information in two orders:Equating these expressions and using symmetry of mutual information and conditional mutual information givesThere is no further independence condition. Treating this part as a strict inequality would obscure its cancellation.

For probability mass functions on the finite alphabet, take logarithms to base two and define the relative entropy byA term with $q_i=0$ is zero, including $p_i=0$; a term with $q_i>0=p_i$ is $+\infty$. Fix $p_i>0$ and write $f_i(t)=t{\log }_2(t/p_i)$. For $t>0$,Thus $f_i$ is a convex function on $[0,\infty )$ by continuous extension to zero. For $0\le \lambda \le 1$, applying this scalar convexity to each coordinate and summing provesIf $p$ has zero coordinates, the finite-valued domain consists of probability mass functions supported on $\{i:p_i>0\}$; it is convex and the same proof applies there. Outside that domain the right side is infinite whenever an offending probability mass function has a positive mixture weight, so the extended-valued convexity assertion still holds. At mixture weights zero or one the inequality is an identity, without needing the expression $0\cdot \infty$.

Index correction: the printed definition only permits $i\le n$, although the required average includes $i=n+1$. Extend the same deletion formula to $1\le i\le n+1$. Without that extension the final summand is undefined; there is no new sample or different estimator to supply.

For a fixed outcome of the sample and a fixed symbol $x$, put $A_j=1_{\{X_j=x\}}$. The leave-one-out empirical distribution then satisfiesDividing by $n+1$ gives ${\hat{p}}_{n+1}=(n+1{)}^{-1}{\sum }_{i=1}^{n+1}{\hat{q}}_{n,i}$. Each of the $n+1$ indicator functions was counted exactly $n$ times before division by $n$. This leave-one-out identity for empirical distributions is deterministic; independence plays no part in this part.

Reference-distribution ambiguity: $\rho$ is not defined in the paper. If it is an arbitrary probability mass function, the printed inequality is false. For instance, choose $p=(1,0)$ and $\rho =(1/2,1/2)$. Every empirical distribution equals $p$, making the printed left side one bit and its right side zero. This is a counterexample for every $n\ge 1$.

Under the consistent interpretation $\rho =p$, the preceding leave-one-out identity for empirical distributions and convexity of relative entropy in its first argument give, for every sample,Deleting any one observation from $n+1$ independent and identically distributed random variables leaves $n$ independent observations with probability mass function $p$. Consequently each ${\hat{q}}_{n,i}$ has the same distribution as ${\hat{p}}_n$. They need not be independent of one another. Taking expected values and using linearity of expectation therefore provesZero coordinates of $p$ are never sampled, almost surely, so the calculation can be restricted to its probability support. In particular the expected values are finite on this finite alphabet.

The discrepancy cannot be removed by silently choosing any fixed reference. Whenever $\rho$ is positive on the probability support of $p$, direct subtraction and $\mathbb{E}{\hat{p}}_n=p$ give the expected relative entropy decompositionThus the valid arbitrary-reference version has $\rho$ on both sides; the printed mixed-reference version has an additional term whose sign prevents the proposed conclusion.

For the maximum entropy distribution on the nonnegative integers, use the geometric distribution counting failures before the first success. Write $r=a/(a+1)$ and defineThe geometric series gives ${\sum }_i{g}_i=1$. Termwise differentiation of a power series applied to that geometric series for $0<r<1$ gives ${\sum }_{i}i{r}^i=r/(1-r{)}^2$, hence ${\sum }_{i}i{g}_i=r/(1-r)=a$.

For any competing probability mass function $p$ of mean $a$, its cross-entropy against $g$ isThis is finite. The fact that finite cross entropy bounds countable information entropy must be justified without assuming in advance that $H(p)$ is finite. Use $\ln u\le u-1$ with $u=g_i/p_i$ when $p_i>0$. Including zero terms by their limiting convention yields, for every finite $N$,Let $N\to \infty$. The information entropy partial sums increase, the cross-entropy partial sums converge to the finite value above, and the final mass difference tends to zero. This proves finiteness and the upper bound. We may now writeRelative entropy nonnegativity has equality exactly when $p=g$. Therefore the displayed geometric probability mass function is the unique maximizer, andThe mean constraint is essential: without it, uniform distributions on longer initial intervals have unbounded information entropy.

The displayed prefix code has expected codeword length $3/2$ ternary digits per source symbol. Instead assignThis is a ternary prefix code: the first two codewords end at distinct tree children of the tree root, and the other two start with $2$ and end at distinct tree children below it. No codeword is a prefix of another. Its expected codeword length isThe reduction is $1/4$ trit per source symbol, which already disproves optimality of the displayed code. The ternary Huffman coding construction below will produce this same improved code tree.

The shape of minimum-cost positive-weight ternary prefix trees arguments in ii–vi assume a full-support finite distribution: $p_i>0$ for every retained source symbol. The printed setup does not state this globally. Each affected solution gives the proof with that qualification and a counterexample when zero-probability symbols are allowed in arbitrary redundant code trees. Part i needs no such qualification.

Exchange the two complete codewords while leaving the code tree unchanged. The prefix code property is preserved because the set of codewords is unchanged. If $p_i>p_j$ but $l_i>l_j$, the change in expected codeword length iscontradicting optimality. Hence $p_i>p_j$ implies $l_i\le l_j$. This probability monotonicity of optimal prefix-code lengths is valid even if some probabilities are zero; equal probabilities impose no order.^[ref]

First assume a full-support finite distribution, as stated above. Let $L$ be the largest codeword length and take a tree leaf at depth $L$. Every existing tree child of its tree parent must also be a tree leaf: an internal tree child would have a descendant deeper than $L$. If the chosen tree leaf were its tree parent's only tree child, moving its symbol to that tree parent would shorten its codeword by one, preserve the prefix code property, and reduce expected codeword length by its positive probability. That contradicts optimality. The tree parent therefore has at least two tree children, both tree leaves. A second codeword has the same first $L-1$ digits and a different last digit, proving the required deepest sibling codeword property for a ternary prefix code.

For the literal wording allowing zero probabilities, take $p=(1,0,0)$ and the prefix code $(0,10,110)$. Its expected codeword length is one, which is minimal: with more than one message an empty codeword is impossible, so the positive-probability message must have length at least one. Yet the deepest tree leaf $110$ has no sibling codeword. Thus positivity or an additional convention removing redundant zero-weight branches is needed.

Suppose a tree parent at depth $n-1$, with $n<L$, has an unused outgoing digit. The missing tree child gives an empty code tree branch at depth $n$. Move any deepest tree leaf into that position, retaining all other codewords and deleting the abandoned empty branch. The new word has no old word as a prefix, because it lies in an unused branch, and it is not a prefix of any retained word. Its length decreases from $L$ to $n$. With a full-support finite distribution this reduces expected codeword length by $p_i(L-n)>0$, contradicting optimality. Hence all three tree children exist, and each has a descendant codeword. In fact every internal vertex above depth $L-1$ has all three tree children. Applying this to the tree parent of the specified prefix gives the claimed three extensions.

The positive-probability qualification attached only to the specified prefix does not by itself suffice. In the zero-weight example $(p,c)=((1,0,0),(0,10,110))$, choose the positive-probability word $0$, so $n=1<L=3$. There is no word starting with $2$. The deepest tree leaf available for relocation has probability zero, so the strict-improvement argument fails. This is why the full-support finite distribution assumption is used for the structural conclusions.

With a full-support finite distribution, suppose two distinct tree parents at depth $L-1$ each have exactly two tree children, both tree leaves. Move one tree leaf from the second pair into the vacant third tree child slot of the first tree parent. Its length remains $L$, so this relocation does not change expected codeword length. The second tree parent now has a single tree child, which is a tree leaf. Replace that remaining tree child's codeword by the tree parent's word. This preserves the prefix code property and shortens a positive-probability codeword by one. Expected codeword length strictly decreases, a contradiction. Thus there is at most one deepest pair with exactly two sibling codewords.

If zero-probability symbols are retained without a reduction convention, the claim can fail. The probability mass function $(1,0,0,0,0)$ with prefix code $(0,100,101,110,111)$ has the optimal expected codeword length one, yet contains the two deepest pairs $(100,101)$ and $(110,111)$. The contraction would only shorten a zero-probability word.

Let $L$ again denote the largest codeword length, and assume a full-support finite distribution. The missing-branch exchange from part iii forces every internal vertex at depth at most $L-2$ to have three tree children. At depth $L-1$, all tree children are tree leaves. Part ii rules out one tree child there; the hypothesis that there is no pair of two deepest sibling codewords rules out two tree children. Thus each such tree parent also has three tree children. Every internal vertex has exactly three tree children, which is a full ternary tree, called semi-complete in this paper. The same last-level argument covers $L=1$.

Without the assumption of a full-support finite distribution the implication is false: for $p=(1,0,0)$, the optimal prefix code $(0,10,110)$ has no deepest pair of two sibling codewords, but its code tree contains vertices with a single tree child. Empty unused tree children are not vertices of the code tree.

Assume a full-support finite distribution. The preceding structural arguments show that every internal vertex has three tree children, except possibly one tree parent at depth $L-1$ with two tree children. Let $N_3$ and $N_2$ count these two kinds of internal vertex. Part iv gives $N_2\in \{0,1\}$; no vertex has one tree child.

A finite rooted tree with $m$ tree leaves has $m+N_2+N_3-1$ edges, while counting outgoing edges gives $2N_2+3N_3$. Equating the counts yieldsFor an odd integer $m$, the right side forces $N_2$ to be an even integer. Since it is at most one, $N_2=0$. Thus no deepest pair has only two sibling codewords, and the optimal code tree is a full ternary tree. This leaf-count identity also directly proves that a full ternary tree has an odd number of tree leaves.

Again the unrestricted zero-weight version is false: $(0,10,11)$ is an optimal prefix code for $p=(1,0,0)$, with odd integer $m=3$, but its two deepest tree leaves form a two-sibling pair. There is no contradiction with the proof because its tree root has only two tree children, which the full-support finite distribution assumption would forbid above the deepest level.

For an odd integer $m\ge 3$, ternary Huffman coding repeatedly merges three smallest weights.

Start with one tree leaf for each source symbol, weighted by its probability. While more than one weighted object remains, choose the three objects with least weights, create their common tree parent with weight equal to their sum, and replace the three by that tree parent. Newly created tree parents participate in subsequent choices. Each merge reduces the number of objects by two; an odd number of objects therefore reaches three and then one, never an unmergeable pair. The final object is the tree root of the code tree.

Label the three outgoing edges at each internal vertex by $0,1,2$ in any order. The digits along the root-to-leaf graph path give each symbol's codeword. Tree leaves cannot be ancestors of other tree leaves, so this is a prefix code. Ties can be resolved arbitrarily. The expected codeword length is measured in trits, and equals the sum of all merge weights, because each merge adds one digit to every codeword below it.

The structural reason for merging three is that the positive-weight, odd-leaf case has a full ternary tree. Its deepest sibling codeword triple can receive the three least weights by exchanging tree leaf labels, and contracting that triple reduces the problem by two symbols. This explains the recursive construction; a separate optimality proof is not required here.

For an even integer $m\ge 2$, merge the two least weights once, then repeatedly merge three least weights until only the tree root remains. The initial binary merge leaves an odd number of weighted objects, so the preceding algorithm applies. The initial merged tree parent has two tree children; subsequent tree parents have three. Equivalently, add one zero-weight dummy symbol, run the odd-leaf ternary Huffman coding algorithm, and remove its codeword afterwards. The dummy contributes nothing to expected codeword length.

Here the first merge joins the two weights $1/8$, producing $1/4$. The three remaining weights are $1/2,1/4,1/4$, and merge directly into the tree root. Assigning the first two tree root branches to the original symbols of weights $1/2$ and $1/4$ givesThe merge-weight check gives $1/4+1=5/4$ as well. For $m=2$, the first merge is already the tree root; for $m=1$, outside this case with an even number of symbols, the usual temporary reduced-problem convention would permit an empty word.

For a discrete memoryless channel with transition probabilities $M(y\mid x)$, the conditional probability of a length-$n$ output given a length-$n$ input factors asThe same transition probabilities apply at each use. Its channel capacity isThe unit is bits per channel use. For finite alphabets the maximum exists by continuity on the probability simplex; with more general alphabets one uses a supremum when appropriate.

An $(m,n)$ channel code consists of an encoder $c:{\mathcal{V}}_m\to {\mathcal{X}}^n$ and a decoder $d:{\mathcal{Y}}^n\to {\mathcal{V}}_m$. It represents each of $m$ messages by $n$ input symbols and recovers a message from the $n$ observed output symbols. Its code rate is $R=({\log }_{2}m)/n$ bits per use. For each message $w$, its conditional error probability is $\mathbb{P}(d(Y^n)\ne w\mid W=w)$; an average error also specifies the message probability distribution, while the maximum error takes the largest conditional error.

Write $T=g(Y)$. Because $T$ is determined by $Y$, the chain rule for mutual information givesThis is the data processing inequality. It holds for every input probability distribution. Maximizing each side over that same set of input probability distributions gives $C_{g(Y)}\le C_Y$; processing cannot increase channel capacity.

A simple sufficient condition for equality is that $g$ be injective on the reachable output alphabet. Then $Y$ can be recovered from $T$, giving $H(Y\mid T)=0$ and hence $I(X;Y\mid T)=0$ for every input law. The input that achieves the original channel capacity therefore achieves it after processing as well. Values of $g$ outside reachable outputs are irrelevant.

Injectivity is sufficient rather than necessary. More precisely, for finite alphabets equality in capacity data processing holds exactly when there is an original capacity-achieving input law for which $X$ and $Y$ have conditional independence given $T$. Sufficiency follows from the displayed gap identity. For necessity, maximize $I(X;T)$ at an input law $p_{\ast }$; if its maximum equals $C_Y$, then $C_Y=I_{p_{\ast }}(X;T)\le I_{p_{\ast }}(X;Y)\le C_Y$, so both inequalities are equalities. Processing may discard output details unrelated to the input without losing channel capacity.

Interpret additive noise in the standard channel sense: $Z$ is independent of the chosen input $X$ and its law is fixed as the input law is varied. A uniform marginal law for $Z$ alone, without this independence assumption, would not specify the transition matrix. Only reachable output symbols are counted.

Translate the output alphabet by $-\min (z_1,z_2)$ and put $d=|z_2-z_1|\ge 1$. The reachable outputs becomeFor $d=1$ the two sets overlap in two points; for $d=2$ in one; for $d\ge 3$ they are disjoint. In particular $|\mathcal{Y}|\ge 4$, and choosing noise values $0,1$ attains four.

With rows indexed by inputs $0,1,2$ and columns by outputs $0,1,2,3$, independence and uniform two-point noise giveEvery conditional output distribution has information entropy one bit, so $I(X;Y)=H(Y)-1\le {\log }_{2}4-1=1$. The input probability mass function $(1/2,0,1/2)$ makes all four outputs equiprobable, attaining that bound. ThusUsing a zero-probability input in a channel-capacity maximization is legitimate; it is unrelated to the strictly positive source weights needed for the tree-shape claims in Question 2.

Each of the three input values has two possible outputs, so their union has at most six elements. The preceding union formula also gives this bound. Choose noise values $0,3$, whose two translated input alphabets are disjoint. With columns ordered $0,1,2,3,4,5$ the transition matrix isThus $|\mathcal{Y}|=6$. Every output determines its input, explicitly $X=Y\mathrm{mod}3$, so $H(X\mid Y)=0$. Consequently $I(X;Y)=H(X)\le {\log }_{2}3$, with equality for a uniform input. ThereforeThe extra uncertainty of which noise value occurred does not reduce information about the input: the two possible outputs for each input remain distinguishable from those of every other input.

Choose noise values $0,2$, giving exactly the outputs $0,1,2,3,4$. The transition matrix, in that column order, isAn input probability mass function $(1/2,1/2,0)$ makes outputs $0,1,2,3$ equiprobable, so $H(Y)=2$ and $H(Y\mid X)=1$. Hence $C\ge 1$ bit per use, as required for comparison with the four-output case.

There is a strict improvement, which can also be computed exactly. Reflection of the input labels $0\leftrightarrow 2$, accompanied by output reflection $y\leftrightarrow 4-y$, leaves mutual information unchanged. Concavity of information entropy makes mutual information a concave function of the input probability mass function for a fixed transition matrix. Averaging an input law with its reflection therefore cannot decrease it. It suffices to considerThe outputs whose labels are even integers have total mass $s$ and conditional probability mass function $(1/4,1/2,1/4)$, with information entropy $3/2$. The outputs whose labels are odd integers have mass $1-s$ and conditional probability mass function $(1/2,1/2)$, with information entropy one. Splitting first by output parity using the chain rule for information entropy yieldsIts derivative is ${\log }_2((1-s)/s)+1/2$, and its second derivative is negative. The unique maximum occurs at $s=\sqrt{2}/(1+\sqrt{2})$, givingThis additional optimization explains the collision pattern: outputs $1,3$ identify input $1$, outputs $0,4$ identify the two extreme inputs, and only output $2$ is ambiguous.

For every input probability mass function, conditional entropy is nonnegative, soTaking the maximum over input laws proves $C\le 1$ bit per channel use. This bound comes from the binary input alphabet itself; no specific transition probabilities or decoder are needed.

There are two possible messages and three channel uses, givingConditional on either transmitted message, a decoding error occurs exactly when at least two of the three bits are flipped. The discrete memoryless channel makes these flips independent, each with probability $\epsilon =1/10$. Their count therefore has a binomial distribution with parameters $3,\epsilon$. Majority-vote decoding of a repetition code givesInterchanging the two bit values leaves the binary symmetric channel and majority decision unchanged, so $\mathbb{P}(\text{error}\mid W=b)=7/250$ as well. Both the maximum conditional error and the average error, for any message prior, are therefore $0.028$. The probability of correct decoding for each message is $243/250=0.972$. These are finite-block error probabilities; a channel-capacity statement alone would not determine them.