Relations between entropy and error probability Export

@article{citeulike:683966, 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-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\⩾C the equivocation achieves its minimal value of R-C at the rate of n^1/2 where n is the block length}, author = {Feder, M. and Merhav, N.}, citeulike-article-id = {683966}, citeulike-linkout-0 = {http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=272494}, journal = {Information Theory, IEEE Transactions on}, keywords = {entropy, error, probability}, number = {1}, pages = {259--266}, posted-at = {2006-06-05 01:54:33}, priority = {2}, title = {Relations between entropy and error probability}, url = {http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=272494}, volume = {40}, year = {1994} }

TY - JOUR ID - citeulike:683966 L3 - citeulike-article-id:683966 N2 - 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-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⩾C the equivocation achieves its minimal value of R-C at the rate of n^1/2 where n is the block length IS - 1 JF - Information Theory, IEEE Transactions on EP - 266 TI - Relations between entropy and error probability VL - 40 SP - 259 KW - entropy KW - error KW - probability AU - Feder, M AU - Merhav, N PY - 1994/// UR - http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=272494 ER -