Herzog–Schönheim conjecture

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 with a joint probability $P(x,y)$. Let e represent an occurrence of error; i.e., that $X\ne Y$. Fano's inequality is

$H(X|Y)\le H(P(e))+P(e)\log (\left|\mathcal{𝒳}\right|-1),$

where $\mathcal{𝒳}$ denotes the support of X,

$H\left(X\right|Y)=-\sum _{i,j}P(x_i,y_j)\log P\left(x_i\right|y_j)$

is the conditional entropy,

$P(e)=P(X\ne Y)$

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,\dots ,f_{r+1}$. Furthermore, the Kullback-Leibler divergence between any pair of densities cannot be too large,

$D_{KL}(f_i\Vert f_j)\le \beta$ for all $i=j.$

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

${\sup }_i{P}_i(\psi (X)=i)\ge 1-\frac{\beta +\log 2}{\log r}$

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 ƒ_θ such that for any θ ≠ θ′

$\Vert f_{\theta }-f_{{\theta }^{\prime }}{\Vert }_{L_1}\ge \alpha ,$

$D_{KL}(f_{\theta }\Vert f_{{\theta }^{\prime }})\le \beta .$

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

${\sup }_{f\in \mathbf{F}}E\Vert f_n-f{\Vert }_{L_1}\ge \frac{\alpha }{2}(1-\frac{n\beta +\log 2}{\log r})$

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

References

• P. Assouad, "Deux 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.
• T. Cover, J. Thomas, Elements of Information Theory. pp. 43.
• 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, 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-387-90523-5