An estimate leaves uncertainty
A decoder can make mistakes even when it has received some information. How does its error probability constrain the uncertainty that remains about the original symbol? We prove a finite-alphabet bound, including the assumptions needed to interpret it.
Let take values in a set of size , and let be a finite-valued observation. A deterministic estimator takes values in . Define if , and otherwise; put . We use logarithms base two and , with endpoint values defined by continuity.
Theorem 12.1.1
(Fano's inequality, finite case)
For any such joint distribution and estimator,
Proof
(Split off the error flag, then average)
Fix a value of positive probability. Since is determined by and , the conditional entropy chain rule gives
For each branch of positive conditional probability: when , is known to equal , so its entropy is zero; when , is restricted to at most other symbols, so its entropy is at most . A zero-probability branch has zero weighted contribution. Writing , including the endpoint cases, yields
Average over . Since is concave, Jensen's inequality gives . The entropy maximum bound gives . Terms for impossible observations contribute nothing.
Proof X-ray
Where the flag, the range of the estimator and concavity enter
Three facts carry the proof. First, is a function of , so adjoining it costs no entropy: , which makes the chain-rule split an identity rather than an inequality. Second, the estimator takes values in : on the error branch avoids , and that is where rather than comes from. Third, the averaging step uses concavity of , so it loses sharpness when the conditional error rates differ. Equality holds exactly when every equals and, on each error branch of positive probability, is uniform on the symbols other than .
A sharp four-symbol example
Worked example 12.1.2
(Symmetric errors can attain the bound)
Let be uniform on . Given , let with probability and let each of the other three values occur with probability . Use . Then . Symmetry makes uniform, and for every observed the conditional distribution of assigns probability to and to each other symbol. Consequently
The first inequality is equality here. The second, looser bound is bits.
When the errors are not spread evenly, the first inequality is strict.
Worked example 12.1.3
(Concentrated errors leave a gap)
Let be uniform on , let with probability and with probability , and use . Then , is uniform by symmetry, and given the symbol is with probability and with probability . Hence
The gap is exactly bits: on the error branch is determined, so the term that allows remaining symbols is not used at all.
Reading the direction correctly
If , the theorem gives : the estimator recovers almost surely. The converse is also true in this finite setting for some estimator: when conditional entropy is zero, each positive-probability observation determines one value. It need not hold for every estimator, since an estimator can deliberately ignore or invert its observation.
Counterexample mode
Zero uncertainty does not make every decoder correct
Let be a fair bit, , and choose the deliberately wrong estimator . Then but . Fano's bound remains valid: for , its right side is . Do not infer that a particular decoder has low error solely from low conditional entropy, or invert the displayed bound without checking the estimator and relevant range.
The bound does not claim an optimal estimator, a coding theorem, or a precise error rate for an unspecified channel. It holds for a stated finite joint distribution and the chosen estimator. Conversely, it can rule out an error rate when the right side at that rate is smaller than the known conditional entropy.
Worked example 12.1.4
(An observation with no information)
Let be uniform on and let be independent of , so bits. Put . Its derivative is positive for , so increases on , and
Fano's bound therefore forces for every estimator; for instance rules out error rate . Guessing a fixed symbol has , so the bound is attained in this degenerate case.
Common mistake
(Dropping the binary-entropy term)
The tempting simplification is false. In the four-symbol example bits while . Knowing whether an error occurred is itself uncertain, and pays for that flag.
Common mistake
(An estimator with an erasure output)
The proof needs . If the decoder may output a symbol , then an error leaves all values possible. For a fair bit , an independent and the decoder that always outputs , one has and , but . With erasures allowed, replace by .
Exercises
Quick check
(For , simplify the first Fano bound. What does it say when ?)
Evaluate .
Solution · Answer
Since , . At zero error the right side is zero.
Quick check
(In the four-symbol example, calculate and state whether the first bound is attained.)
Compare each conditional error distribution with the equality condition.
Solution · Answer
and the first bound is attained, because each conditional error distribution is uniform over the other three symbols and all are .
Quick check
(If is a fair bit and the estimator always outputs , find and .)
Solution · Answer
determines , so , while the estimator is always wrong, so . The bound reads .
Quick check
(When , why is it legitimate to bound by ?)
Count the possible values of on that branch.
Solution
Given and an error, can only be one of the values different from ; a distribution supported on at most that many symbols has entropy at most their logarithm. If the event has probability zero, its weighted contribution is zero.
Further reading
MIT OpenCourseWare, Information Theory Lecture 2 discusses Fano's lemma.