Past exam of the mathematics course of the University of Cambridge / 2014 / iii / Paper 60 / 2

Every conditional output distribution is a permutation of $q$. Since Shannon entropy is invariant under a permutation, its value is the same for every input symbol. Thus, for any input distribution,All Shannon entropies in this solution are in bits. A different fixed logarithm base changes every entropy and capacity by the same constant factor.

The Shannon second coding theorem states that the operational channel capacity of a finite discrete memoryless channel is $C={\max }_{p(x)}I(X:Y)$: rates below this maximum admit block codes with error tending to zero, and rates above it cannot have vanishing error. For this channel the preceding calculation givesusing maximum entropy on a finite alphabet. The transition matrix is a doubly stochastic matrix. Therefore the uniform input has uniform output: $p(y)=\frac{1}{3}{\sum }_{x}p(y\mid x)=1/3$. It achieves the entropy upper bound, and henceEquivalently this is the weakly symmetric channel capacity theorem: permutations of a common row and equal column sums make the uniform input optimal. If $q$ is uniform, the output contains no information about the input and the formula gives zero.

The error indicator is a Bernoulli random variable with probabilities $P(Z=1)=p_e$ and $P(Z=0)=1-p_e$. Its Shannon entropy is therefore the binary entropyUse $0{\log }_{2}0=0$, so this expression also covers error probabilities zero and one.

Apply the definitions of conditional entropy and insert $H(X,Y)$:Inserting $H(Z,Y)$ instead gives the alternative chain rule for conditional entropyBoth are expansions of the same joint conditional uncertainty, with the variables exposed in opposite orders.

Because $Z$ is determined by $X,Y$, its conditional entropy satisfies $H(Z\mid X,Y)=0$. Equate the two forms of the chain rule for conditional entropy to obtainConditioning cannot increase classical Shannon entropy: $H(Z)-H(Z\mid Y)=I(Z:Y)\ge 0$ by nonnegativity of mutual information. Thus $H(Z\mid Y)\le H(Z)=h(p_e)$. When $Z=0$, the value of $X$ is exactly $f(Y)$ and $H(X\mid Y,Z=0)=0$. When $Z=1$ and $Y=y$, the value $f(y)$ is excluded, leaving at most $|J_X|-1$ possibilities. By maximum entropy on a finite alphabet,Averaging the two conditional cases now yieldsand consequentlyThis is Fano's inequality via an error indicator. Events of zero probability contribute zero to the average and need no conditional distribution. For $|J_X|=1$, the inference is automatically correct and the entropy is zero; the displayed logarithmic form is intended for $|J_X|\ge 2$. Optimality of the guess is not needed for the inequality: it holds for every deterministic $f$.