Fano's Inequality

Fano's Inequality bounds the minimal achievable probability of error Pe when estimating a discrete random variable X from observations Y in terms of the conditional entropy H(X|Y) and the alphabet size |X|. A common form is H(Pe)+Pe·log(|X|-1) ≥ H(X|Y), where H(Pe) is the binary entropy of Pe.