Past exam of the communication Theory course of the University of Oxford / 2011 (B11a, DMAB 2650, DMCN 2650, DMPB 2650, DMST 2650)

Source paper: FOI request thread. The cover identifies Communication Theory, B11a, Friday 24 June 2011, 2.30pm to 4.00pm. Its four readable pages are original private Part B bundle pages 312–315.

Use the continuous convention $0{\log }_2(0/q)=0$. Let $S=\{r:p_r>0\}$. Applying the allowed logarithm inequality to $q_r/p_r$ for $r\in S$ givesHence $d(p,q)\ge 0$. Equality forces ${\sum }_{r\in S}{q}_r=1$. Since every $q_r$ is strictly positive, this makes $S$ the entire alphabet. Equality in every weighted logarithm inequality then forces $q_r/p_r=1$ for every $r$. Conversely $p=q$ makes every summand zero. ThusThis is Gibbs inequality for relative entropy, with zero probabilities in the first argument handled explicitly.

For the uniform distribution $u_r=1/n$, direct expansion givesPart (a) therefore proveswith equality exactly for $p_X(r)=1/n$ for every $r$. Thus the uniform distribution is the unique entropy maximizer.

Normalize the candidate distribution by settingThe supplied finite sum gives its meanThus it meets the constraint. Since ${\log }_2{q}_r={\log }_{2}c-r$, every other distribution $p$ with mean $m$ satisfiesNonnegativity and the equality case in part (a) proveThe maximum is unique; the entropy comparison uses the fixed mean rather than an unconstrained optimization.

The given logarithmic moment iswhere the $r=1$ term is zero. It is attained by the positive distributionwhose probabilities sum to one. Write $A=2/[n(n+1)]$, so ${\log }_2{q}_r={\log }_{2}A+{\log }_{2}r$. For any distribution $p$ with the required logarithmic moment,Consequently the unique maximizer and its entropy areThe increasing weights are consistent with the prescribed moment; they need not be a decreasing power law.

Write $w_i=(Aq{)}_i$. For each row put $S_i=\{j:a_{ij}>0\}$; the positive row entries ${\alpha }_i=(a_{ij}{)}_{j\in S_i}$ form a probability distribution because the row sum is one. When $w_i>0$, define the probability distributionPart (a), applied on this row support, gives $d(r_i,{\alpha }_i)\ge 0$. Its weighted sum expands asRows with $w_i=0$ contribute zero, since all $a_{ij}{q}_j$ in such a row vanish. Using the convention that zero-weight logarithmic terms are zero, the result isBoth stochasticity conditions have a role: row sums normalize the comparison distributions, while column sums preserve the total contribution from $q$.

This is entropy increase under doubly stochastic mixing.

A binary code assigns a finite binary word $c_k$ to each source symbol $x_k$. In the ordinary unframed convention these codewords are nonempty. It is uniquely decodable when concatenation gives an injective map from finite symbol strings to bit strings:The decoder can recover the entire symbol sequence without being told where codewords end. This is stronger than merely assigning distinct words to individual symbols.

An instantaneous code can decode each symbol as soon as its final bit arrives, without waiting for later bits. Equivalently it is prefix-free: no codeword is a proper prefix of another, and different symbols receive different codewords.

For nonempty codewords, decoding greedily from the start of the bit string identifies the first codeword unambiguously; repeating identifies the whole sequence. Thus an instantaneous code is uniquely decodable under the ordinary nonempty-word convention.

The codeword lengths are integers. For necessity, take $L={\max }_k{l}_k$ and view codewords as nodes of the binary tree. A codeword of length $l_k$ has $2^{L-l_k}$ descendant words at depth $L$. Prefix-freeness makes these descendant sets disjoint, soFor sufficiency, reorder the lengths nondecreasingly. Assign words successively. At depth $l_k$, words extending previously assigned codewords numberThe asserted inequality, even after dropping the later nonnegative terms, givesThus at least one depth-$l_k$ word does not extend an earlier word. Choose it. Since lengths are nondecreasing, it cannot be a proper prefix of a shorter earlier word, and equal-length duplicates have been excluded. Induction constructs the required code. Therefore Kraft inequality is necessary and sufficient:

First consider any instantaneous code. Put $K_0={\sum }_k{2}^{-l_k}\le 1$ and $q_k=2^{-l_k}/K_0$. Part 1(a) givesso $\mathbb{E}L\ge H(X)-{\log }_2{K}_0\ge H(X)$.

For the construction, take the Shannon lengths $l_k=\lceil -{\log }_2{p}_k\rceil$. Then $2^{-l_k}\le p_k$, so Kraft's condition holds. Also $l_k<-{\log }_2{p}_k+1$ for every $k$. Averaging givesFor a nontrivial alphabet all $p_k<1$, so these lengths are positive and the ordinary code convention applies. For a deterministic one-symbol source, the usual zero-bit convention uses $l_1=0$ when the number of source symbols is externally known. If strictly nonempty codewords and arbitrary unframed message lengths are required instead, that degenerate case has $\mathbb{E}L\ge 1$ and cannot satisfy the printed strict upper bound. This convention issue does not affect sources with at least two symbols.

Let $F_k={\sum }_{r<k}{p}_r$ and let $J_k=[F_k,F_k+p_k)$ be the probability cell of symbol $k$. Its midpoint is $G_k=F_k+p_k/2$. Use the binary expansion terminating in zeros at a dyadic rational, so truncation to $l_k$ bits givesThe chosen codeword corresponds to the dyadic interval $D_k=[a_k,a_k+2^{-l_k})$. It contains $G_k$, and its width satisfies $2^{-l_k}\le p_k/2$. ConsequentlyThus $D_k\subseteq J_k$. The probability cells are disjoint, so the code intervals are disjoint. If one binary codeword were a prefix of another, its dyadic interval would contain the other's interval, contradicting this disjointness. Hence the code is instantaneous.

Finally, $l_k=\lceil -{\log }_2{p}_k\rceil +1<-{\log }_2{p}_k+2$. Multiplying by $p_k$ and summing yieldsThis is the Shannon-Fano-Elias code: the extra bit makes the dyadic interval narrow enough to remain inside the cell around its midpoint.

For finite-valued random variables, their mutual information isEquivalently,with zero joint-probability terms omitted. It is the relative entropy of the joint law from the product of its marginals and is nonnegative, with equality exactly when the two variables are independent.

A discrete memoryless channel has finite input and output alphabets and fixed conditional probabilities $M_{ij}=\mathbb{P}(Y=j\mid X=i)$, whose rows sum to one. Memorylessness means that for successive uses, conditional on the input sequence, the output probabilities factor as the product of these one-use conditional probabilities.

Its information capacity in bits per use isThe maximization varies the input distribution while keeping the channel matrix fixed. The output distribution is $p_{X}M$ in the row-vector convention.

Let $B$ be the selected block, and write $\alpha =\mathbb{P}(B=1)$. Because both the input and output alphabets are disjoint across blocks, $B$ is determined by either the input or the output. The mutual-information chain rule therefore givesFor any fixed $\alpha$, equality is achievable by using a capacity-achieving distribution inside each block. It remains to maximize this binary expression.

Put $S=2^{C_1}+2^{C_2}$ and $r=2^{C_1}/S$. A direct expansion of binary relative entropy yieldsPart 1(a) makes the maximum ${\log }_{2}S$, uniquely at $\alpha =r$. HenceThe block choice itself communicates information, in addition to any information sent within the selected block.

This is capacity of a disjoint sum of channels.

There are three distinguishable output groups: columns $\{1,2\}$ can arise only from input one; column $\{3\}$ can arise from inputs two or three, whose rows are identical; and columns $\{4,5\}$ can arise only from input four.

Each group has zero internal channel capacity. A block with one input cannot carry a variable input choice, and the middle block has identical output laws for both of its inputs. Combining the three disjoint zero-capacity blocks therefore givesEquivalently, the output identifies exactly which of these three groups was used, so mutual information is the entropy of that group label. It is maximized when all group probabilities are one third. The capacity-achieving input distributions are preciselySplitting the middle probability arbitrarily cannot communicate an extra distinction because its two channel rows agree.

For any chosen input distribution, the chain rule and nonnegativity of conditional mutual information giveand likewise $I(U;V,W)\ge I(U;W)$. Choosing an input distribution attaining either marginal capacity proves $K\ge \max \{K_1,K_2\}$.

For the upper bound, conditional independence implies $H(V,W\mid U)=H(V\mid U)+H(W\mid U)$, while entropy subadditivity gives $H(V,W)\le H(V)+H(W)$. ThereforeMaximizing over the input law givesMore precisely, under the conditional-independence assumption,The outputs may be dependent through the common input, and this final term measures the information they share rather than add independently.

This is information from two conditionally independent observations.