# Fano's inequality

# Fano's inequality

In information theory, **Fano's inequality** (also known as the **Fano converse** and the **Fano lemma**) relates the average information lost in a noisy channel to the probability of the categorization error. It was derived by Robert Fano in the early 1950s while teaching a Ph.D. seminar in information theory at MIT, and later recorded in his 1961 textbook.

It is used to find a lower bound on the error probability of any decoder as well as the lower bounds for minimax risks in density estimation.

`Let therandom variables`

*X*and*Y*represent input and output messages with ajoint probability. Let*e*represent an occurrence of error; i.e., that, withbeing an approximate version of. Fano's inequality is`wheredenotes the support of`

*X*,is the conditional entropy,

is the probability of the communication error, and

is the corresponding binary entropy.

Alternative formulation

`Let`

*X*be arandom variablewithdensityequal to one ofpossible densities. Furthermore, theKullback–Leibler divergencebetween any pair of densities cannot be too large,- for all

`Letbe an estimate of the index. Then`

`whereis theprobabilityinduced by`

Generalization

The following generalization is due to Ibragimov and Khasminskii (1979), Assouad and Birge (1983).

Let **F** be a class of densities with a subclass of *r* + 1 densities *ƒ**θ* such that for any *θ* ≠ *θ*′

Then in the worst case the expected value of error of estimation is bound from below,

where *ƒ**n* is any density estimator based on a sample of size *n*.

## References

*Transmission of information: a statistical theory of communications*

*Transmission of information: a statistical theory of communications*