= Solution
Given an output $y$ of positive <probability>, the ideal observer chooses a symbol maximizing the posterior:
$$
\boxed{g(y)\in\operatorname*{arg\,max}_{x\in A}P(X=x\mid Y=y).}
$$
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_xP(X=x\mid Y=y)$. Then $w(y)=1-\Pi_y$. Applying the two cases from part (b) to the posterior distribution gives
$$
H(X\mid Y=y)\geq2(1-\Pi_y)=2w(y).
$$
Average with respect to the output law to obtain the <conditional entropy upper bound on minimum decoding error>:
$$
\boxed{\mathbb Ew(Y)\leq\frac12H(X\mid Y).}
$$
This is an upper bound on the optimum error <probability>; it does not hold for arbitrary deliberately poor decoding rules.
Back to article page
