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

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.