Relations between entropy and error probability

1994/01/01 by M. Feder, Meir Feder, Neri Merhav +1 · 24 citations
Engineering · Computer Science · #Wireless Communication Security Techniques #Error Correcting Code Techniques #Computability, Logic, AI Algorithms

paper · doi:10.1109/18.272494

Abstract

The relation between the entropy of a discrete random variable and the minimum attainable probability of error made in guessing its value is examined. While Fano's inequality provides a tight lower bound on the error probability in terms of the entropy, the present authors derive a converse result/spl mdash/a tight upper bound on the minimal error probability in terms of the entropy. Both bounds are sharp, and can draw a relation, as well, between the error probability for the maximum a posteriori (MAP) rule, and the conditional entropy (equivocation), which is a useful uncertainty measure in several applications. Combining this relation and the classical channel coding theorem, the authors present a channel coding theorem for the equivocation which, unlike the channel coding theorem for error probability, is meaningful at all rates. This theorem is proved directly for DMCs, and from this proof it is further concluded that for R/spl ges/C the equivocation achieves its minimal value of R/spl minus/C at the rate of n/sup 1/spl sol/2/ where n is the block length.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>

Cited by

• A New Approach of Deriving Bounds between Entropy and Error from Joint Distribution: Case Study for Binary Classifications
• General Classes of Lower Bounds on the Probability of Error in Multiple Hypothesis Testing
• Extremal Relations Between Shannon Entropy and ℓ_α-Norm
• Exact upper and lower bounds on the misclassification probability
• Generative causal explanations of black-box classifiers
• DyFormer: A Scalable Dynamic Graph Transformer with Provable Benefits on Generalization Ability
• A review of feature selection methods based on mutual information
• LeanML: A Design Pattern To Slash Avoidable Wastes in Machine Learning\n Projects
• Analytical Bounds between Entropy and Error Probability in Binary Classifications
• An Information Theoretic Study of Timing Side Channels in Two-user Schedulers
• Prediction-based Online Trajectory Compression
• Source and Channel Polarization over Finite Fields and Reed-Solomon Matrices
• Estimating information in time-varying signals. [europepmc]
• Information Theoretic Approaches for Motor-Imagery BCI Systems: Review and Experimental Comparison. [europepmc]
• Bayesian Input Design for Linear Dynamical Model Discrimination. [europepmc]
• A Security Enhanced Encryption Scheme and Evaluation of Its Cryptographic Security. [europepmc]
• Generalizations of Fano's Inequality for Conditional Information Measures via Majorization Theory. [europepmc]
• Error Exponents and α -Mutual Information. [europepmc]
• An Approach for Security Enhancement of Certain Encryption Schemes Employing Error Correction Coding and Simulated Synchronization Errors. [europepmc]
• Refinery 4.0, a Review of the Main Challenges of the Industry 4.0 Paradigm in Oil & Gas Downstream. [europepmc]
• The Interplay between Error, Total Variation, Alpha-Entropy and Guessing: Fano and Pinsker Direct and Reverse Inequalities. [europepmc]
• Effects of External Stimulation on Psychedelic State Neurodynamics. [europepmc]
• Duality between predictability and reconstructability in complex systems. [europepmc]
• Meditation and complexity: a review and synthesis of evidence. [europepmc]

Related

• A note on the expected minimum error probability in equientropic channels
• Minimum MS. E. Gerber's Lemma
• Analytical Bounds between Entropy and Error Probability in Binary Classifications
• The Principle of Uncertain Maximum Entropy
• Arimoto-Rényi Conditional Entropy and Bayesian M-ary Hypothesis Testing