Skip to main content

Probability Estimation in the Rare-Events Regime

Author(s): Wagner, Aaron B; Viswanath, Pramod; Kulkarni, Sanjeev R

To refer to this page use:
Abstract: We address the problem of estimating the probability of an observed string that is drawn i.i.d. from an unknown distribution. Motivated by models of natural language, we consider the regime in which the length of the observed string and the size of the underlying alphabet are comparably large. In this regime, the maximum likelihood distribution tends to overestimate the probability of the observed letters, so the Good–Turing probability estimator is typically used instead. We show that when used to estimate the sequence probability, the Good–Turing estimator is not consistent in this regime. We then introduce a novel sequence probability estimator that is consistent. This estimator also yields consistent estimators for other quantities of interest and a consistent universal classifier.
Publication Date: 23-May-2011
Citation: Wagner, Aaron B, Viswanath, Pramod, Kulkarni, Sanjeev R. (2011). Probability Estimation in the Rare-Events Regime. IEEE Transactions on Information Theory, 57 (6), 3207 - 3229. doi:10.1109/tit.2011.2137210
DOI: doi:10.1109/tit.2011.2137210
ISSN: 0018-9448
EISSN: 1557-9654
Pages: 3207 - 3229
Type of Material: Journal Article
Journal/Proceeding Title: IEEE Transactions on Information Theory
Version: Author's manuscript

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.