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.

Fano's inequality

Let the random variables "X" and "Y" represent input and output messages (out of "r"+1 possible messages) with a joint probability $P(x,y).$ The Fano's inequality is:$H(X|Y)leq\; H(e)+P(e)log(r),$

where :$Hleft(X|Y\; ight)=sum\_\{i,j\}\; P(x\_i,y\_j)log\; Pleft(x\_i|y\_j\; ight)$

is the conditional entropy,:$P(e)=sup\_i\; sum\_\{j\; ot=i\}\; P(y\_j|x\_i)$

is the probability of the communication error, and:$H(e)=P(e)log\; P(e)+(1-P(e))log(1-P(e))$

is the corresponding binary entropy.

Alternative formulation

Let "X" be a random variable with density equal to one of $r+1$ possible densities $f\_1,ldots,f\_\{r+1\}$. Furthermore, the Kullback-Leibler divergence between any pair of densities can not be too large,: for all $i\; ot\; =\; j.$

Let $psi(X)in\{1,ldots,\; r+1\}$ be an estimate of the index. Then

:where $P\_i$ is the probability induced by $f\_i$

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 $f\_\; heta$ such that for any $heta\; ot\; =\; heta,\text{'}$

:$|f\_\{\; heta\}-f\_\{\; heta\text{'}\}|\_\{L\_1\}geq\; alpha,$:Then in the worst case the expected value of error of estimation is bound from below,

:where $f\_n$ is any density estimator based on a sample of size "n".

References

* P. Assouad, "Deus remarques sur l'estimation," "Comptes Rendus de L'Academie des Sciences de Paris", Vol. 296, pp. 1021-1024, 1983.

* L. Birge, "Estimating a density under order restrictions: nonasymptotic minimax risk," Technical report, UER de Sciences Economiques, Universite Paris X, Nanterre, France, 1983.

* L. Devroye, "A Course in Density Estimation". Progress in probability and statistics, Vol 14. Boston, Birkhauser, 1987. ISBN 0-8176-3365-0, ISBN 3-7643-3365-0.

* R. Fano, "Transmission of information; a statistical theory of communications." Cambridge, Mass., M.I.T. Press, 1961. ISBN 0-262-06001-9

* R. Fano, " [http://www.scholarpedia.org/article/Fano_inequality Fano inequality] " Scholarpedia, 2008.

* I. A. Ibragimov, R. Z. Has′minskii, "Statistical estimation, asymptotic theory". Applications of Mathematics, vol. 16, Springer-Verlag, New York, 1981. ISBN 0-3879-0523-5