Fano's inequality


In information theory, Fano's inequality 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 the random variables and represent input and output messages with a joint probability. Let represent an occurrence of error; i.e., that, with being an approximate version of. Fano's inequality is
where denotes the support of,
is the conditional entropy,
is the probability of the communication error, and
is the corresponding binary entropy.

Alternative formulation

Let be a random variable with density equal to one of possible densities. Furthermore, the Kullback–Leibler divergence between any pair of densities cannot be too large,
Let be an estimate of the index. Then
where is the probability induced by

Generalization

The following generalization is due to Ibragimov and Khasminskii, Assouad and Birge.
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.