Let take values in an alphabet of size , let be an estimate determined by , and put . Thenwhere is the binary entropy function. The error indicator costs at most bits, and after an error there are at most possible values of .
Articles by others on the same topic
Fano's inequality is a result in information theory that provides a lower bound on the probability of error in estimating a message based on observed data. It quantifies the relationship between the uncertainty of a random variable and the minimal probability of making an incorrect estimation of that variable when provided with some information. More formally, consider a random variable \( X \) with \( n \) possible outcomes and another random variable \( Y \), which represents the "guess" or estimation of \( X \).