 Conditional entropy upper bound on minimum decoding error

For finite random variables $X,Y$, let $P_e$ be the error probability of maximum a posteriori decoding of $X$ from $Y$. Then $P_e\le H(X\mid Y)/2$ when conditional entropy is measured in bits. At each positive-probability output $y$, the optimum success probability is the largest posterior atom ${\Pi }_y$, so its conditional error is $1-{\Pi }_y$. Apply the entropy lower bound from the largest atom to that posterior to get $2(1-{\Pi }_y)\le H(X\mid Y=y)$, then average over $Y$. An arbitrary decoder need not satisfy this bound; it uses the optimum conditional decision rule.