2006/08/22 by Nandakishore Santhi, Santhi, Nandakishore, Alexander Vardy +1 · 2 citations
Computer Science · Mathematics · #Chaos-based Image/Signal Encryption #Discrete Mathematics (cs.DM) #E.4 #Error Correcting Code Techniques #FOS: Computer and information sciences #Information Theory (cs.IT) #Numerical Methods and Algorithms #cs.DM #cs.IT #math.IT
paper · pdf · doi:10.48550/arxiv.cs/0608087
8 pages, 6 figures, To be presented at the 44-th Annual Allerton Conference on Communication, Control, and Computing, September 2006
arxiv created 2006/08/22 · openalex publication_date 2006/08/22 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider the problem of estimating the probability of error in multi-hypothesis testing when MAP criterion is used. This probability, which is also known as the Bayes risk is an important measure in many communication and information theory problems. In general, the exact Bayes risk can be difficult to obtain. Many upper and lower bounds are known in literature. One such upper bound is the equivocation bound due to Rényi which is of great philosophical interest because it connects the Bayes risk to conditional entropy. Here we give a simple derivation for an improved equivocation bound. We then give some typical examples of problems where these bounds can be of use. We first consider a binary hypothesis testing problem for which the exact Bayes risk is difficult to derive. In such problems bounds are of interest. Furthermore using the bounds on Bayes risk derived in the paper and a random coding argument, we prove a lower bound on equivocation valid for most random codes over memoryless channels.