Past exam of the communication Theory course of the University of Oxford / 2010 / 2

For finite-valued random vectors, write $p(x,y)=P(X=x,Y=y)$ and $p_Y(y)=P(Y=y)$. The conditional entropy is the average entropy of the posterior distributions:Equivalently, $H(X\mid Y)=-{\sum }_{x,y:p(x,y)>0}p(x,y){\log }_{2}p(x\mid y)$. Since $p(x,y)=p_Y(y)p(x\mid y)$, splitting the logarithm givesUse the usual convention $0{\log }_{2}0=0$ and omit conditionals at zero-probability outputs. The same identities hold for countable alphabets whenever the entropy sums are well-defined, without subtracting two infinite quantities.

Set $Z=g(X)$. Given $X$, the value of $Z$ is certain, so $H(Z\mid X)=0$. Applying the entropy identity in the two orders givesbecause conditional entropy is nonnegative. ConsequentlyA deterministic coarsening can merge distinguishable source outcomes, but cannot create additional Shannon entropy.

Choose a most probable symbol $x_{\ast }$, and let $B=1_{\{X=x_{\ast }\}}$. Its binary entropy isSince $B$ is a function of $X$, part (a)(ii) gives $H(X)\ge h_2(\Pi )$. On $[1/2,1]$, the concave function $h_2$ lies above the chord joining $(1/2,1)$ and $(1,0)$. That chord has height $2(1-\Pi )$. ThereforeThe endpoint $\Pi =1$ is included by continuity and corresponds to a deterministic source.

Every positive atom has probability at most $\Pi$, so $-{\log }_{2}p(x)\ge -{\log }_2\Pi$. Averaging yieldsFor $0<\Pi \le 1/2$, the supplied inequality $4\Pi \le 4^{\Pi }$ gives $2+{\log }_2\Pi \le 2\Pi$. Rearranging provesThe two regimes combine into the entropy lower bound from the largest atom, valid for every finite probability distribution.

Given an output $y$ of positive probability, the ideal observer chooses a symbol maximizing the posterior:Ties may be broken arbitrarily, and the choice at an impossible output does not matter. This is maximum a posteriori decoding. It minimizes conditional error at each $y$, because a deterministic decision $x$ is correct with probability $P(X=x\mid Y=y)$; a randomized decision is a weighted average of these success probabilities and cannot exceed their maximum.

Write ${\Pi }_y={\max }_{x}P(X=x\mid Y=y)$. Then $w(y)=1-{\Pi }_y$. Applying the two cases from part (b) to the posterior distribution givesAverage with respect to the output law to obtain the conditional entropy upper bound on minimum decoding error:This is an upper bound on the optimum error probability; it does not hold for arbitrary deliberately poor decoding rules.