Fano's inequality
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. Let the random variables formula_1 and formula_2 represent input and output  messages with a joint probability formula_3. Let formula_4 represent an occurrence of error; i.e., that formula_5, with formula_6 being an approximate version of formula_1. Fano's inequality is where formula_9 denotes the support of formula_1, is the conditional entropy, is the probability of the communication error, and is the corresponding binary entropy. Proof. Define an indicator random variable formula_14, that indicates the event that our estimate formula_6 is in error, Consider formula_17. We can use the chain rule for entropies to expand this in two different ways Equating the two Expanding the right most term, formula_20 Since formula_22 means formula_23 ; being given the value of formula_24 allows us to know the value of formula_1 with certainty. This makes the term formula_26. On the other hand, formula_27 means that formula_28, hence given the value of formula_24, we can narrow down formula_1 to one of formula_31 different values, allowing us to upper bound the conditional entropy formula_32. Hence The other term, formula_34, because conditioning reduces entropy. Because of the way formula_14 is defined, formula_36, meaning that formula_37. Putting it all together, Because formula_39 is a Markov chain, we have formula_40 by the data processing inequality, and hence formula_41, giving us Alternative formulation . Let formula_1 be a random variable with density equal to one of formula_44 possible densities formula_45. Furthermore, the Kullback–Leibler divergence between any pair of densities cannot be too large, Let formula_48 be an estimate of the index. Then where formula_50 is the probability induced by formula_51 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 "θ" ≠ "θ"<nowiki>′</nowiki> Then in the worst case the expected value of error of estimation is  bound from below, where "ƒ" is any density estimator based on a sample of size "n".