Note to users. If you're seeing this message, it means that your browser cannot find this page's style/presentation instructions -- or possibly that you are using a browser that does not support current Web standards. Find out more about why this message is appearing, and what you can do to make your experience of our site the best it can be.

Science 17 October 2003:
Vol. 302. no. 5644, pp. 427 - 431
DOI: 10.1126/science.1088284
Prev | Table of Contents | Next

Reports

Always Good Turing: Asymptotically Optimal Probability Estimation

Alon Orlitsky,1,2* Narayana P. Santhanam,1 Junan Zhang1

While deciphering the Enigma code, Good and Turing derived an unintuitive, yet effective, formula for estimating a probability distribution from a sample of data. We define the attenuation of a probability estimator as the largest possible ratio between the per-symbol probability assigned to an arbitrarily long sequence by any distribution, and the corresponding probability assigned by the estimator. We show that some common estimators have infinite attenuation and that the attenuation of the Good-Turing estimator is low, yet greater than 1. We then derive an estimator whose attenuation is 1; that is, asymptotically it does not underestimate the probability of any sequence.

1 Department of Electrical and Computer Engineering, University of California, San Diego, La Jolla, CA 92093, USA.
2 Department of Computer Science and Engineering, University of California, San Diego, La Jolla, CA 92093, USA.

* To whom correspondence should be addressed. E-mail: alon{at}ucsd.edu

Read the Full Text


THIS ARTICLE HAS BEEN CITED BY OTHER ARTICLES:
The hematopoietic stem compartment consists of a limited number of discrete stem cell subsets.
H. B. Sieburg, R. H. Cho, B. Dykstra, N. Uchida, C. J. Eaves, and C. E. Muller-Sieburg (2006)
Blood 107, 2311-2316
   Abstract »    Full Text »    PDF »


To Advertise     Find Products

Science. ISSN 0036-8075 (print), 1095-9203 (online)