A better good-turing estimator for sequence probabilities

Aaron B. Wagner, Pramod Viswanath, Sanjeev R. Kulkarni

Research output: Chapter in Book/Report/Conference proceedingConference contribution

10 Scopus citations

Abstract

We consider the problem of estimating the probability of an observed string drawn i.i.d. from an unknown distribution. The key feature of our study is that the length of the observed string is assumed to be of the same order as the size of the underlying alphabet. In this setting, many letters are unseen and the empirical distribution tends to overestimate the probability of the observed letters. To overcome this problem, the traditional approach to probability estimation is to use the classical Good-Turing estimator. We introduce a natural scaling model and use it to show that the Good-Turing sequence probability estimator is not consistent. We then introduce a novel sequence probability estimator that is indeed consistent under the natural scaling model.

Original languageEnglish (US)
Title of host publicationProceedings - 2007 IEEE International Symposium on Information Theory, ISIT 2007
Pages2356-2360
Number of pages5
DOIs
StatePublished - Dec 1 2007
Event2007 IEEE International Symposium on Information Theory, ISIT 2007 - Nice, France
Duration: Jun 24 2007Jun 29 2007

Publication series

NameIEEE International Symposium on Information Theory - Proceedings
ISSN (Print)2157-8101

Other

Other2007 IEEE International Symposium on Information Theory, ISIT 2007
CountryFrance
CityNice
Period6/24/076/29/07

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Information Systems
  • Modeling and Simulation
  • Applied Mathematics

Fingerprint Dive into the research topics of 'A better good-turing estimator for sequence probabilities'. Together they form a unique fingerprint.

Cite this