Fano Bounds for Finite Hypothesis Identification

From Information to Identification Error

Suppose data come from one of finitely many candidate models, and an estimator must identify which model generated them. When the models are difficult to distinguish, identification error cannot be small for every candidate. Fano’s inequality makes this idea quantitative: it relates error probability to how much information the data carry about the true hypothesis.

For a usable lower bound, we need to control that information using quantities determined by the candidate distributions. The largest pairwise Kullback–Leibler divergence gives a simple uniform control. The resulting argument applies to any finite collection of distributions; it does not require a parametric model or a special form for the estimator.

Definition: Let $M\geq 2$, and let $P_1,\ldots,P_M$ be distributions for the observed data $Z$. The identification problem has an unknown index $J\in\{1,\ldots,M\}$, with $Z\mid J=j\sim P_j$. An identification rule $\hat J=\hat J(Z)$ has error probability $P(\hat J\neq J)$. Unless stated otherwise, take $J$ to be uniform on the $M$ indices.

Write $I(J;Z)$ for the mutual information between the index and the data, and use natural logarithms. Under the uniform prior, the entropy of $J$ is $H(J)=\log M$. Fano’s inequality says that small error requires the data to reveal nearly all of this uncertainty.

Fano’s inequality: For any identification rule and uniform $J$, $$ P(\hat J\neq J)\ \geq\ 1-\frac{I(J;Z)+\log 2}{\log M}. $$ Because error probability is nonnegative, the right-hand side can be replaced by its positive part $\left[1-(I(J;Z)+\log 2)/\log M\right]_+$.

For completeness, let $E=\mathbf{1}\{\hat J\neq J\}$. Since $\hat J$ is determined by $Z$, conditioning on $Z$ determines $\hat J$. Given $E=0$ and $Z$, the index $J$ is known. Given $E=1$ and $Z$, at most $M-1$ indices remain possible. The conditional entropy chain rule therefore gives

H(J\mid Z) \leq H(E\mid Z)+H(J\mid E,Z) \leq \log 2+P(E=1)\log(M-1) \leq \log 2+P(E=1)\log M.

Using $I(J;Z)=H(J)-H(J\mid Z)$ and $H(J)=\log M$, rearrangement yields the displayed inequality. This proof allows any deterministic rule. If a rule uses independent randomization, include its random seed with $Z$; that seed contains no information about $J$, so the same bound applies.

Controlling Information by Pairwise Divergence

Let $\bar P=M^{-1}\sum_{j=1}^M P_j$ be the mixture distribution of the data under the uniform prior. The mutual information has the representation

I(J;Z)=\frac{1}{M}\sum_{j=1}^M D_{\mathrm{KL}}(P_j\Vert \bar P).

To connect this expression to pairwise divergences, choose one candidate distribution as a reference. The identity below shows that the average divergence to any reference distribution is at least the mutual information.

Identity: If $Q$ is a distribution such that the divergences below are finite, then $$ \frac{1}{M}\sum_{j=1}^M D_{\mathrm{KL}}(P_j\Vert Q) = I(J;Z)+D_{\mathrm{KL}}(\bar P\Vert Q). $$ Consequently, $I(J;Z)\leq M^{-1}\sum_jD_{\mathrm{KL}}(P_j\Vert Q)$.

To verify the identity, take densities $p_j,\bar p,q$ with respect to a common dominating measure. Since $\bar p=M^{-1}\sum_jp_j$, expand the left-hand side and split the logarithm:

\begin{aligned} \frac{1}{M}\sum_j\int p_j\log\frac{p_j}{q} &=\frac{1}{M}\sum_j\int p_j\log\frac{p_j}{\bar p} +\frac{1}{M}\sum_j\int p_j\log\frac{\bar p}{q}\\ &=I(J;Z)+\int \bar p\log\frac{\bar p}{q}\\ &=I(J;Z)+D_{\mathrm{KL}}(\bar P\Vert Q). \end{aligned}

The second equality uses the mixture identity $M^{-1}\sum_jp_j=\bar p$. Nonnegativity of Kullback–Leibler divergence then gives the inequality. In particular, set $Q=P_1$. If all ordered pairwise divergences are finite, every term $D_{\mathrm{KL}}(P_j\Vert P_1)$ is bounded by their largest value.

Theorem: Finite-hypothesis Fano bound. Suppose $M\geq2$, $J$ is uniform on $\{1,\ldots,M\}$, and $Z\mid J=j\sim P_j$. Define the largest ordered pairwise divergence $$ D_{\max}=\max_{1\leq j,k\leq M}D_{\mathrm{KL}}(P_j\Vert P_k). $$ If $D_{\max}<\infty$, then every identification rule satisfies $$ P(\hat J\neq J)\geq \left[1-\frac{D_{\max}+\log 2}{\log M}\right]_+. $$

Indeed, the identity with $Q=P_1$ gives $I(J;Z)\leq M^{-1}\sum_jD_{\mathrm{KL}}(P_j\Vert P_1)\leq D_{\max}$. Substituting this into Fano’s inequality proves the claim. If $D_{\max}$ is infinite, the displayed expression supplies no nontrivial lower bound; the finite-divergence assumption is what makes the result useful.

The maximum is over ordered pairs because Kullback–Leibler divergence is generally asymmetric. When the data are $n$ independent observations from one of the candidate distributions, the product-sample identity gives $D_{\mathrm{KL}}(P_j^{\otimes n}\Vert P_k^{\otimes n})=nD_{\mathrm{KL}}(P_j\Vert P_k)$. Thus a single-observation divergence bound scales linearly with sample size.

Worked Applications

Worked Example: Four Gaussian Location Hypotheses

Suppose one observation has distribution $N(\mu_j,1)$, where the four possible means are $-0.3,-0.1,0.1,0.3$. The goal is to identify the mean. For two normal distributions with the same variance $1$, the divergence is $D_{\mathrm{KL}}(N(\mu,1)\Vert N(\nu,1))=(\mu-\nu)^2/2$. The largest absolute difference between candidate means is $0.3-(-0.3)=0.6$, so

D_{\max}=\frac{(0.6)^2}{2}=0.18.

Here $M=4$, so $\log M=\log4\approx1.3863$ and $\log2\approx0.6931$. The theorem gives

P(\hat J\neq J) \geq 1-\frac{0.18+0.6931}{1.3863} \approx 1-0.6298 =0.3702.

Thus, averaged over the four equally likely hypotheses, every rule has error at least about $0.37$. Since the largest divergence is between the two extreme means, using only the nearest-neighbour separation would not justify this particular bound.

Worked Example: Eight Categorical Hypotheses with Two Observations

Let one observation take values in $\{1,\ldots,8\}$. Under hypothesis $j$, assign probability $0.3$ to outcome $j$ and probability $0.1$ to each of the other seven outcomes. Observe two independent draws and identify $j$. For distinct hypotheses $j$ and $k$, only coordinates $j$ and $k$ differ in the divergence:

D_{\mathrm{KL}}(P_j\Vert P_k) =0.3\log\frac{0.3}{0.1} +0.1\log\frac{0.1}{0.3} +6(0.1)\log\frac{0.1}{0.1} =0.2\log3\approx0.2197.

The value is the same in either direction, so this is the maximum single-observation divergence. For two independent draws, the maximum divergence is $2(0.2\log3)=0.4\log3\approx0.4394$. With $M=8$, $\log8\approx2.0794$, and therefore

P(\hat J\neq J) \geq 1-\frac{0.4394+0.6931}{2.0794} \approx 0.455.

Even though each hypothesis gives its own outcome the largest probability, two observations do not guarantee reliable identification. The bound formalizes that limitation without requiring a particular decoding rule.

Worked Example: Identical Distributions and a Weak Bound

Suppose there are $M=4$ hypotheses, but the data distribution is the same under all four: $P_1=P_2=P_3=P_4=R$. Every pairwise divergence is zero, so the theorem yields

P(\hat J\neq J)\geq 1-\frac{\log2}{\log4}=\frac12.

In this example the exact uniform-prior error is at least $3/4$. The data have the same distribution whatever the index, so the output of any rule is independent of the uniform index $J$. Its probability of being correct is therefore $1/4$, and its error probability is $1-1/4=3/4$. The Fano bound is valid but not sharp: the additive $\log2$ term can make it conservative, especially for a small number of hypotheses.

From Average Error to a Minimax Bound

The theorem uses a uniform prior to measure average error over the finite set. This immediately gives a worst-case lower bound. For any rule,

\max_{1\leq j\leq M}P_j(\hat J\neq j) \ \geq\ \frac{1}{M}\sum_{j=1}^M P_j(\hat J\neq j) \ \geq\ \left[1-\frac{D_{\max}+\log2}{\log M}\right]_+.

The first inequality holds because a maximum is at least the average. Consequently, taking the infimum over all identification rules preserves the lower bound on the smallest possible worst-case error. This is the decision-theoretic value of the calculation: it rules out uniformly reliable identification whenever the candidate distributions are insufficiently separated in information.

Common Pitfalls and Interpretation

Using the nearest pair instead of the largest divergence. The theorem needs a uniform upper bound on information across all hypotheses. A small divergence for one pair does not control the other candidates.
Ignoring direction. In general $D_{\mathrm{KL}}(P_j\Vert P_k)\neq D_{\mathrm{KL}}(P_k\Vert P_j)$. The stated $D_{\max}$ includes both directions.
Reading a weak lower bound as a failure of the method. If $D_{\max}+\log2\geq\log M$, the bound is nonpositive before taking its positive part and gives no information. That does not imply accurate identification is possible; it only means this inequality does not certify a positive error lower bound.
Confusing average and worst-case error. Fano’s inequality is applied under the uniform prior. The worst-case statement follows because worst-case error is at least this uniform average.

Key takeaway: For $M$ finite hypotheses, control the information in the data by the largest ordered pairwise Kullback–Leibler divergence. Fano’s inequality then gives an explicit lower bound on average—and hence worst-case—identification error.

Check Your Understanding

Use the definitions and bounds above to answer these questions.

Why must the pairwise maximum account for both $D_{\mathrm{KL}}(P_j\Vert P_k)$ and $D_{\mathrm{KL}}(P_k\Vert P_j)$?
If $M=8$ and $D_{\max}=0.2$, write the finite-hypothesis Fano lower bound before evaluating it.
For $n$ independent observations, how does the largest pairwise divergence change when the one-observation maximum is $d$?
Why does a uniform-prior average-error lower bound imply the same lower bound on worst-case error?
What does a nonpositive Fano lower bound tell you—and what does it not tell you—about identification accuracy?