  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.
