Always Good Turing: Asymptotically Optimal Probability Estimation

See allHide authors and affiliations

Science  17 Oct 2003:
Vol. 302, Issue 5644, pp. 427-431
DOI: 10.1126/science.1088284

You are currently viewing the abstract.

View Full Text


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.

View Full Text