Lower bound on the error probability for families with bounded likelihood ratios

Author:
Andrew L. Rukhin

Journal:
Proc. Amer. Math. Soc. **119** (1993), 1307-1314

MSC:
Primary 62C05; Secondary 62F11, 62F15, 62F35

DOI:
https://doi.org/10.1090/S0002-9939-1993-1166361-X

MathSciNet review:
1166361

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: In the classification problem a new sharp lower bound for the error probability is derived. This bound depends only on the prior probabilities and on the support of pairwise likelihood ratios.

**[1]**Richard Bellman,*Introduction to matrix analysis*, Second edition, McGraw-Hill Book Co., New York-Düsseldorf-London, 1970 (Russian). MR**0258847****[2]**Moshe Ben-Bassat and Josef Raviv,*Rényi’s entropy and the probability of error*, IEEE Trans. Information Theory**IT-24**(1978), no. 3, 324–331. MR**0484747****[3]**Abraham Berman and Robert J. Plemmons,*Nonnegative matrices in the mathematical sciences*, Academic Press [Harcourt Brace Jovanovich, Publishers], New York-London, 1979. Computer Science and Applied Mathematics. MR**544666****[4]**J. T. Chu and J. D. Chueh,*Inequalities between information measures and error probability*, J. Franklin Inst.**282**(1966), 121–125. MR**0199043**, https://doi.org/10.1016/0016-0032(66)90359-0**[5]**Thomas M. Cover, Michael A. Freedman, and Martin E. Hellman,*Optimal finite memory learning algorithms for the finite sample problem*, Information and Control**30**(1976), no. 1, 49–85. MR**0405927****[6]**R. G. Gallager,*Information theory and reliable communication*, Wiley, New York, 1968.**[7]**Martin E. Hellman and Thomas M. Cover,*Learning with finite memory*, Ann. Math. Statist**41**(1970), 765–782. MR**0272100**, https://doi.org/10.1214/aoms/1177696958**[8]**A. Rényi,*On some problems of statistics from the point of view of information theory*, Proc. Colloquium on Information Theory (Debrecen, 1967) János Bolyai Math. Soc., Budapest, 1968, pp. 343–357. MR**0246424****[9]**I. Vajda,*Theory of statistical inference and information*, Kluwer, Dordrecht, 1989.

Retrieve articles in *Proceedings of the American Mathematical Society*
with MSC:
62C05,
62F11,
62F15,
62F35

Retrieve articles in all journals with MSC: 62C05, 62F11, 62F15, 62F35

Additional Information

DOI:
https://doi.org/10.1090/S0002-9939-1993-1166361-X

Keywords:
Classification problem,
error probability,
likelihood ratios,
linear programming,
M-matrix

Article copyright:
© Copyright 1993
American Mathematical Society