On the Interplay Between Conditional Entropy and Error Probability

Fano's inequality relates the error probability of guessing a finitely-valued random variableXgiven another random variableYand the conditional entropy ofXgivenY. It is not necessarily tight when the marginal distribution ofXis fixed. This paper gives a tight upper bound on the conditional entropy ofXgivenYin terms of the error probability and the marginal distribution ofX. A new lower bound on the conditional entropy for countably infinite alphabets is also found. The relationship between the reliability criteria of vanishing error probability and vanishing conditional entropy is also discussed. A strengthened form of the Schur-concavity of entropy which holds for finite or countably infinite random variables is given.