Converse theorems and Fano's inequality

Let W take values in an alphabet of size M at least two, and let the estimate be a function of the observation Y. Introduce an error indicator E. Conditional on Y and E=0, the message is known from the estimate. Conditional on an error, at most M−1 alternatives remain. Expanding the conditional entropy with E and bounding its entropy by the binary entropy of the overall error probability yields Fano's inequality.

This entropy inequality does not require a uniform message law. Uniformity becomes important when converting it into a communication-rate bound, because then H(W)=log₂M. If a highly skewed message is guessed correctly almost always without observing the channel, its small error does not imply that log₂M bits were communicated. Independent randomized decoder coins can be included in the observation, preserving the relevant Markov structure and the same argument.

For a finite DMC without feedback or input constraints, a code induces the Markov chain W to Xⁿ to Yⁿ. Data processing bounds message information by input–output information. The entropy chain rule and memorylessness bound this block quantity by the sum of one-use mutual informations, each at most capacity. Input symbols need not be independent for this upper bound. The conditional product structure of the channel is what limits the total to nC.

For equiprobable messages, substitute the information budget into H(W)=I(W;Yⁿ)+H(W given Yⁿ). The loose form of Fano then produces the displayed finite-block lower bound. If the right side is negative, it says no more than the usual nonnegativity of error. If the block rate approaches a fixed value greater than C, the limiting bound is positive. That proves that vanishing error is impossible, but it does not force error to approach one.

A strong converse is a separate conclusion that error tends to one above capacity, and requires a stronger argument than this loose Fano estimate. The inequality also does not determine an optimal finite-block error or establish a sharp threshold at exactly capacity. Finite-block achievability and converse bounds can leave a gap that depends on length and the desired reliability. Equality in an entropy bound should not be assumed merely because its terms can be evaluated.

In statistical inference, a related use constructs a finite set of well-separated parameter candidates and bounds the information available about their index. Fano then bounds the chance of identifying the candidate, which can be translated into an estimation loss using the separation. That reduction needs a specified candidate distribution and a justified separation-to-loss implication. A message error inequality alone does not automatically give a minimax lower bound for an unrelated continuous parameter problem.