Why Information Limits Classification
Suppose an unknown index \(W\) is chosen from \(M\) possibilities, and an observation \(Z\) is used to predict it. If \(Z\) reveals little about \(W\), no classifier can reliably identify the index. Fano’s inequality makes this limitation quantitative: it lower-bounds classification error using the information \(Z\) contains about \(W\).
The result is useful when a statistical problem can be reduced to identifying one of finitely many hypotheses. Its central quantity is mutual information, which measures the reduction in uncertainty about the index after observing the data. This tutorial proves the inequality for a uniform index and works through examples that show both its meaning and its limitations.
Setup and Definitions
Let \(M\geq 2\), let \(W\) be uniform on \(\{1,\ldots,M\}\), and let \(Z\) be an observation whose distribution may depend on \(W\). A classifier is a measurable function \(\hat W=\delta(Z)\) taking values in \(\{1,\ldots,M\}\). Its probability of error is \(P_e=P(\hat W\neq W)\). All logarithms below are natural logarithms, so entropies and mutual information are measured in nats.
The conditional probabilities in this definition are posterior probabilities. Because \(W\) takes finitely many values, they can be represented by the conditional expectations \(P(W=j\mid Z)\), whether or not \(Z\) itself is discrete. Thus the definition does not require the observation to have a probability mass function.
A Finite-Support Entropy Bound
The proof of Fano’s inequality uses a basic fact: a random variable supported on at most \(k\) values has entropy at most \(\log k\). Here is a short derivation. Let \(q\) be its probability vector, omitting zero-probability values if desired, and let \(u\) be the uniform distribution on \(k\) values. Nonnegativity of the relative entropy gives \(D(q\|u)=\sum_{i:q_i>0}q_i\log(q_i/u_i)\geq 0\). For completeness, \(-\log x\geq 1-x\) for \(x>0\), so \[ \sum_{i:q_i>0}q_i\log(q_i/u_i) \geq \sum_{i:q_i>0}q_i(1-u_i/q_i) =1-\sum_{i:q_i>0}u_i \geq 0. \] Since \(u_i=1/k\), this yields \(D(q\|u)=\log k-H(q)\), and therefore \(H(q)\leq\log k\). The same bound applies conditionally whenever the conditional distribution is supported on at most \(k\) values.
We also use the binary entropy function \(h(p)=-p\log p-(1-p)\log(1-p)\), for \(0\leq p\leq 1\). It is concave: on \(0<p<1\), \(h''(p)=-1/[p(1-p)]<0\), and it extends continuously to the endpoints. Jensen’s inequality therefore gives \(E[h(Q)]\leq h(E[Q])\) for any random variable \(Q\) in \([0,1]\).
Fano’s Inequality
To prove the result, define the error indicator \(E=\mathbf{1}\{\hat W\neq W\}\). Given \(W\) and \(Z\), the value of \(E\) is determined. Thus \(H(E\mid W,Z)=0\), and the conditional entropy chain rule gives \[ H(W\mid Z)=H(E,W\mid Z)=H(E\mid Z)+H(W\mid E,Z). \] Write \(p=P_e=P(E=1)\). If \(r(Z)=P(E=1\mid Z)\), then \(H(E\mid Z)=E[h(r(Z))]\leq h(E[r(Z)])=h(p)\), by the concavity of binary entropy and the law of total expectation.
It remains to bound \(H(W\mid E,Z)\). When \(E=0\), the value of \(W\) is exactly \(\hat W=\delta(Z)\), so its conditional entropy is zero. When \(E=1\), knowing \(Z\) determines \(\hat W\), and \(W\) must be one of the other \(M-1\) indices. Its conditional entropy is therefore at most \(\log(M-1)\), by the finite-support entropy bound. Averaging over \(E\) gives \[ H(W\mid E,Z) =P(E=0)H(W\mid E=0,Z)+P(E=1)H(W\mid E=1,Z) \leq (1-p)\cdot 0+p\log(M-1). \] Combining this with \(H(E\mid Z)\leq h(p)\) proves \(H(W\mid Z)\leq h(p)+p\log(M-1)\). \(\square\)
A widely used error-probability form follows by using \(h(p)\leq\log 2\) and \(\log(M-1)\leq\log M\): \[ \log M-I(W;Z)\leq\log 2+P_e\log M. \] Rearranging yields the usual lower bound
Since a probability cannot be negative, the bound can be stated with the right-hand side replaced by its maximum with zero. This simpler form is sometimes loose; the preceding entropy inequality retains more information about the error probability.
Worked Examples
Worked Example: A Symmetric Four-Hypothesis Channel
Let \(M=4\), let \(W\) be uniform, and suppose the observation \(Y\) equals \(W\) with probability \(0.8\). With probability \(0.2\), it is each of the other three indices with equal probability. Find the optimal classification error and mutual information, and check Fano’s inequality.
For any \(y\), the posterior probabilities are \(P(W=y\mid Y=y)=0.8\) and \(P(W=j\mid Y=y)=0.2/3\) for each \(j\neq y\). The largest posterior probability is \(0.8\), so the classifier \(\hat W=Y\) is optimal. It makes an error exactly when the channel changes the index, giving \(P_e=0.2\).
By symmetry, \(Y\) is also uniform. The conditional entropy is \[ H(W\mid Y)=-(0.8\log 0.8)-3(0.2/3)\log(0.2/3) =h(0.2)+0.2\log 3. \] Numerically, \(h(0.2)\approx0.5004\) and \(0.2\log 3\approx0.2197\), so \(H(W\mid Y)\approx0.7201\). Thus \(I(W;Y)=\log4-H(W\mid Y)\approx1.3863-0.7201=0.6662\).
The exact Fano inequality holds with equality here: \(H(W\mid Y)=h(P_e)+P_e\log3\). The simpler error lower bound is \(P_e\geq1-(0.6662+0.6931)/1.3863\approx0.0195\), which is valid but much weaker than the actual error \(0.2\).
Worked Example: An Observation Independent of the Index
Let \(W\) be uniform on five indices, and suppose \(Z\) is independent of \(W\). Determine the smallest possible classification error and compare it with the usual Fano bound.
Independence means that \(P(W=j\mid Z)=1/5\) for every index \(j\), almost surely. Whatever index a classifier outputs after seeing \(Z\), its conditional probability of being correct is \(1/5\). Therefore every classifier has error \(P_e=1-1/5=4/5\), and this error is attainable.
Because \(Z\) provides no information about \(W\), \(H(W\mid Z)=H(W)=\log5\) and \(I(W;Z)=0\). The usual Fano bound gives \(P_e\geq1-\log2/\log5\approx1-0.4307=0.5693\). This is below, and therefore consistent with, the actual minimum error \(0.8\). The example illustrates that a valid information-based lower bound need not be sharp.
Worked Example: Observing Which Group Contains the Index
Let \(W\) be uniform on \(\{1,\ldots,8\}\), and let \(Z\) report whether \(W\) lies in \(\{1,2,3,4\}\) or in \(\{5,6,7,8\}\). Find the best classification error and the information in \(Z\).
Given either reported group, the four indices in that group remain equally likely. A classifier’s conditional probability of being correct is at most \(1/4\): it is \(1/4\) if the classifier outputs an index in the reported group, and zero if it outputs an index outside that group. Thus a classifier choosing any member of the reported group attains the highest possible conditional accuracy \(1/4\), and the minimum error is \(P_e=3/4\).
The group label is equally likely to take either value, so \(H(Z)=\log2\). Because \(Z\) is determined by \(W\), \(H(Z\mid W)=0\), and \(I(W;Z)=H(Z)=\log2\). Equivalently, \(H(W\mid Z)=\log4\): after observing the group, four indices remain equally likely.
The usual Fano bound gives \(P_e\geq1-(\log2+\log2)/\log8=1-2/3=1/3\). The actual error \(3/4\) is larger. In particular, the conditional accuracy is not \(1/4\) for every possible output: an output outside the reported group has conditional accuracy zero. The relevant fact for the optimal error is that \(1/4\) is an upper bound on conditional accuracy, attained by choosing within the group.
Interpretation and Common Pitfalls
The theorem says that small mutual information forces substantial error when the number of possible indices is large. If \(I(W;Z)\) is much smaller than \(\log M\), the observation has not removed much of the initial uncertainty \(\log M\). The conditional entropy remains high, and Fano’s inequality prevents any classifier from having a very small error probability.
Several details matter when applying the result:
- Reversing the inequality. Fano bounds conditional entropy from above in terms of error, \(H(W\mid Z)\leq h(P_e)+P_e\log(M-1)\). Substituting \(H(W\mid Z)=\log M-I(W;Z)\) and rearranging yields a lower, not an upper, bound on error.
- Using the wrong number of alternatives after an error. Once the classifier’s output is known and an error has occurred, the true index has at most \(M-1\) possibilities, not \(M\). This is why the sharper inequality contains \(\log(M-1)\).
- Confusing a lower bound with an exact error rate. The simple bound may be weak or even negative before it is truncated at zero. A weak bound does not imply a mistake in the argument; it may mean the mutual-information estimate is not strong enough for the desired conclusion.
- Assuming every output within a reported group behaves alike to an output outside it. Conditional correctness depends on where the classifier’s output lies. For a uniform group of four, choosing an index inside gives probability \(1/4\) of correctness, while choosing outside gives probability zero.
For a randomized classifier, the same conclusion follows by including its independent random seed as part of the observation. The seed is independent of \(W\), so it does not increase \(I(W;Z)\); the resulting prediction is a deterministic function of the augmented observation. This preserves the information-based error bound.
Check Your Understanding
Try these questions using the definitions and proof above.
- Why does uniformity of \(W\) imply \(H(W)=\log M\)?
- In the proof, why can \(W\) take at most \(M-1\) values when \(E=1\) and \(Z\) is known?
- For \(M=2\), what is the value of \(\log(M-1)\), and what does the exact Fano inequality become?
- If \(I(W;Z)=0\) and \(M=5\), what lower bound does the usual Fano form give on \(P_e\)?
- In the group example, what is the conditional probability of correct classification if a classifier outputs an index outside the reported group? Why?