Past exam of the communication Theory course of the University of Oxford / 2011 / 3

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.