Fano inequality converts small information into unavoidable error. It is one of the main converse tools connecting information theory with statistical lower bounds.
Decoding error
Definition. Let \(M\) be uniform on \(\{1,\ldots,N\}\), let \(Y\) be an observation, and let \(\widehat M=\widehat M(Y)\). The probability of error is \(P_e=P(\widehat M\ne M)\).
Fano inequality
Theorem. For every decoder, \[ H(M\mid Y)\le h_2(P_e)+P_e\log(N-1), \] where \(h_2(u)=-u\log u-(1-u)\log(1-u)\). Consequently, \[ P_e\ge 1-\frac{I(M;Y)+1}{\log N} \] when logarithms are base two. With natural logarithms, replace \(1\) by \(\log 2\).
Proof by error indicator
Proof. Let \(E=\mathbf 1\{M\ne\widehat M\}\). Since \(E\) is determined by \((M,Y)\), \[ H(M\mid Y)=H(E,M\mid Y)-H(E\mid M,Y)\le H(E)+H(M\mid E,Y). \] On \(E=0\), \(M\) is determined by \(Y\). On \(E=1\), at most \(N-1\) values remain. This gives the displayed bound.
Statistical lower bounds
Remark. In minimax estimation one chooses a separated finite packing of parameters, places a uniform prior on it, and applies Fano to the induced testing problem. The resulting lower bound is controlled by mutual information or average KL divergence.
Fano's inequality
Theorem. Let \(V\) take values in an \(M\)-point set and let \(\widehat V=\widehat V(X)\). If \(P_e=P(\widehat V\ne V)\), then \[ H(V\mid X)\le h_2(P_e)+P_e\log(M-1). \] If \(V\) is uniform, \[ P_e\ge1-\frac{I(V;X)+\log2}{\log M}. \]
Proof. Let \(E=\mathbf1\{\widehat V\ne V\}\). Because \(E\) is determined by \((V,X)\), \[ H(V\mid X)=H(E,V\mid X)-H(E\mid V,X) =H(E\mid X)+H(V\mid E,X). \] The first term is at most \(h_2(P_e)\). If \(E=0\), \(V\) is known; if \(E=1\), at most \(M-1\) values remain, giving the first display. For uniform \(V\), \(H(V\mid X)=\log M-I(V;X)\), use \(h_2(P_e)\le\log2\) and \(\log(M-1)\le\log M\), then rearrange.
Nonuniform Fano inequality
Corollary. For arbitrary \(V\), \[ P_e\ge \frac{H(V)-I(V;X)-\log2}{\log(M-1)}. \] The bound is useful only when the prior entropy is large; cardinality alone can be misleading for concentrated priors.
Metric estimation reduction
Theorem. Let \(\theta_1,\ldots,\theta_M\) be \(2\delta\)-separated under metric \(d\), let \(V\) be uniform, and draw \(X\sim P_{\theta_V}\). Then every estimator satisfies \[ \sup_jP_{\theta_j}\{d(\widehat\theta,\theta_j)\ge\delta\} \ge1-\frac{I(V;X)+\log2}{\log M}. \]
Proof. Decode \(\widehat V\) as the nearest packing point to \(\widehat\theta\). If \(d(\widehat\theta,\theta_V)<\delta\), separation makes the nearest point uniquely \(V\). Thus decoding error is contained in the estimation-error event. Apply Fano and note that worst-case error dominates average error.
Bounding the information by pairwise KL
Proposition. If \(\overline P=M^{-1}\sum_jP_j\), then \[ I(V;X)=\frac1M\sum_jD(P_j\|\overline P) \le\frac1{M^2}\sum_{j,k}D(P_j\|P_k). \]
Proof. The equality is the expected posterior-change representation. Convexity of \(D(P_j\|\cdot)\) in its second argument gives \[ D(P_j\|\overline P) \le\frac1M\sum_kD(P_j\|P_k). \] Average over \(j\).
A reference-distribution bound
Proposition. For any reference law \(Q\), \[ I(V;X)\le\frac1M\sum_jD(P_j\|Q). \]
Proof. The mixture \(\overline P\) minimizes \(\frac1M\sum_jD(P_j\|Q)\) over \(Q\), because \[ \frac1M\sum_jD(P_j\|Q) = I(V;X)+D(\overline P\|Q). \]
List decoding
Theorem. If a decoder outputs a list \(\mathcal L(X)\) of at most \(L\) candidates and \(P_e=P\{V\notin\mathcal L(X)\}\), then \[ H(V\mid X) \le h_2(P_e)+(1-P_e)\log L+ P_e\log M. \]
Proof. Let \(E\) indicate whether \(V\) is outside the list. Given \(E=0,X\), there are at most \(L\) possibilities; given \(E=1,X\), at most \(M\). Decompose conditional entropy through \(E\) as in the ordinary Fano proof.
When Fano is weak
Fano is effective for large finite packings whose pairwise distributions are hard to distinguish. It can be weak for two-point problems, very small error probabilities, or losses not naturally reduced to exact decoding. Le Cam's method, Assouad's lemma, hypothesis-testing divergences, or rate-distortion versions of Fano may then be sharper.
Rate-distortion Fano principle
Proposition. Let \(V\sim\pi\) and let \(\widehat V\) satisfy \(\mathbb E d(V,\widehat V)\le D\). By the definition of the rate-distortion function, \[ I(V;\widehat V)\ge R_\pi(D). \] Since \(V\to X\to\widehat V\), \[ I(V;X)\ge R_\pi(D). \] Therefore any \(D\) with \(R_\pi(D)>I(V;X)\) is unattainable.
This form replaces a packing reduction by the exact information required to reproduce the parameter within average distortion \(D\).