TY - GEN

T1 - A better good-turing estimator for sequence probabilities

AU - Wagner, Aaron B.

AU - Viswanath, Pramod

AU - Kulkarni, Sanjeev R.

PY - 2007

Y1 - 2007

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=51649116866&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=51649116866&partnerID=8YFLogxK

U2 - 10.1109/ISIT.2007.4557571

DO - 10.1109/ISIT.2007.4557571

M3 - Conference contribution

AN - SCOPUS:51649116866

SN - 1424414296

SN - 9781424414291

T3 - IEEE International Symposium on Information Theory - Proceedings

SP - 2356

EP - 2360

BT - Proceedings - 2007 IEEE International Symposium on Information Theory, ISIT 2007

T2 - 2007 IEEE International Symposium on Information Theory, ISIT 2007

Y2 - 24 June 2007 through 29 June 2007

ER -