= 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\leq 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)\leq H(X\mid Y=y)$, then average over $Y$. An arbitrary decoder need not satisfy this bound; it uses the optimum conditional decision rule.
Back to article page
