# Generalizing Fano's inequality

Fano's inequality says the following:

Theorem: Let $$X$$ be a random variable with range $$M$$. Let $$\hat{X} = g(Y)$$ be the predicted value of $$X$$ given some transmitted value $$Y$$, where $$g$$ is a deterministic function. Let $$p_e$$ be the probability of making a mistake, i.e., $$p_e = Pr[ \hat{X} \ne X ]$$. Then $$p_e \ge \frac{H(X\mid Y) - 1}{\log|M|}$$.

It seems to me that Fano's inequality is useful when $$X$$ is the output of an algorithm computing some function, i.e., for any fixed input there is a unique correct output.

I'm interested in the following generalization: Suppose we are trying to reconstruct a valid output for a problem, where, for a given input $$I$$, there are multiple valid solutions. In other words, for each input $$I$$, there is a fixed subset $$S_I$$ of values that are correct, i.e., if $$\hat{X} \in S_I$$ we succeed (instead of just $$\hat{X} = X$$). For instance, $$\hat{X}$$ could be a spanning tree of a given input graph $$I$$, and $$S_I$$ would be the set of all spanning trees.

How would I bound the error probability of recovering any element in $$S_I$$?