Fano Decoding Entropy Bound
Relate decoding errors to conditional entropy and separate channel noise from optimal decoding.
By Riano · Published · Updated · Report a correction
Fano Decoding Entropy Bound
Fano's inequality relates the probability of error in guessing a discrete random variable to its conditional entropy. It quantifies how much uncertainty remains about a transmitted message even after observing the received signal.
Worked example: 3 classes with 25% error
Consider predicting a label from 3 uniform classes with a MAP decoder and a channel error probability of 0.25. The conditional entropy depends on both the error probability and the number of classes.
- Calculate the entropy of the uniform prior over q = 3 classes: H(X) = ln(3) ≈ 1.09861229 nats.
- Compute the binary entropy of the error indicator for e = 0.25: h(0.25) = −0.25 ln(0.25) − 0.75 ln(0.75) ≈ 0.56233514 nats.
- Evaluate the Fano conditional entropy upper bound: H(X|Y) = h(e) + e ln(q − 1) = h(0.25) + 0.25 ln(2) ≈ 0.56233514 + 0.17328680 = 0.73562194 nats, with mutual information I(X; Y) = H(X) − H(X|Y) ≈ 0.36299035 nats.
Reproduce the bound
Open the Fano Decoding Entropy Bound module.
- Select Classes 3 and Channel error 0.25.
- Observe that the Fano entropy upper bound matches the Conditional entropy nats.
Limitations
This demonstration assumes symmetric noise distribution among alternative labels. Fano's inequality is a general bound, but it may be loose for asymmetric channels or nonuniform priors.
References
For an in-depth treatment of Fano's inequality and its applications in information theory, refer to the Stanford course notes: Stanford STATS 311 full notes.
Experience it interactively
Adjust parameters, observe in real time, and build deep intuition with Riano’s interactive Fano Decoding Entropy Bound module.
Try Fano Decoding Entropy Bound on Riano →