A Better Good-Turing Estimator for Sequence Probabilities
A Better Good-Turing Estimator
for Sequence Probabilities
Aaron B. Wagner
School of ECE
Cornell University
wagner@ece.cornell.edu
Pramod Viswanath
ECE Department
University of Illinois
at Urbana-Champaign
pramodv@uiuc.edu
Sanjeev R. Kulkarni
EE Department
Princeton University
kulkarni@princeton.edu
Abstract— We consider the problem of estimating the prob-
ability 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.
I. INTRODUCTION
Suppose we are given a string drawn i.i.d. from an un-
known distribution. Our goal is to estimate the probability
of the observed string. One approach to this problem is to
use the type, or empirical distribution, of the string as an
approximation of the true underlying distribution and then to
calculate the resulting probability of the observed string. It
is well known that this estimator assigns to each string its
largest possible probability under an i.i.d. distribution. For
large enough observation sizes, this estimator works well;
indeed, for large n and a fixed underlying distribution, it is
a consistent sequence probability estimator.
Motivated by applications in natural language, we focus
on a nonstandard regime in which the size of the underlying
alphabet is of the same order as the length of the observed
string. In this regime, the type of the observation is a poor
representation of the true probability distribution. Indeed,
many letters with nonzero probability will not be observed
at all and the type will obviously assign these letters zero
probability. This would not make for a consistent probability
estimator.
Since probability estimation and compression are closely
related, we can turn to the compression literature for suc-
cor. The results in this literature are negative, however. For
instance, Orlitsky and Santhanam [1] shows that universal
compression of i.i.d. strings drawn from an alphabet that grows
linearly with the observation size is impossible. As such, the
compression literature is unhelpful and even suggests that
seeking a consistent universal sequence probability estimator
might be futile.
Nevertheless, sequence probability estimation is of such im-
portance in applications that several heuristic approaches have
been developed. The foremost among them is based on the
classical Good-Turing probability estimator (see Section IV).
The idea is to use the Good-Turing estimator instead of the
type to estimate the underlying probability distribution. The
probability of the sequence can then be calculated accordingly.
Orlitsky et al. [3] have studied the performance of a similar
scheme in the context of probability estimation for patterns. No
theoretical results regarding the performance of this approach
for sequence probability estimation are available, however.
To analyze the performance of this scheme, we introduce
a natural scaling model in which the number of observations,
n, and the underlying alphabet size grow at the same rate.
Further, the underlying probabilities vary with n. The only
restriction we make is that no letter should be either too rare
or too frequent. That is, the probability that any given symbol
occurs somewhere in the string should be bounded away from
0 and 1 as the length of the string tends to infinity. In particular,
this condition requires that the probabilities of the letters be
Θ(1/n). We call this the rare events regime. This scaling
model is formally described in the next section.
Our model is similar to the one used by Klaassen and
Mnatsakanov [4] and Khmaladze and Chitashvili [5] to study
related problems. We used this model previously [6] to show
consistency of the Good-Turing estimate of the total probabil-
ity of letters that occur a given number of times in the observed
string. In the present paper, we use this model to first show that
the Good-Turing estimator for sequence probabilities performs
poorly; in fact, a simple example illustrates that it is not
consistent. Drawing from this example, we then provide a
novel sequence probability estimator that improves upon the
Good-Turing estimator—in fact, we show that it is consistent
in the context of the natural scaling model. This is done in
Section V. Finally, we discuss the application of our results to
universal hypothesis testing problems in the rare event regime
in Section VI.
http://arxiv.org/abs/0704.1455v2
II. THE RARE EVENTS REGIME
Let Ωn be a sequence of finite alphabets. For each n, let
pn and qn be probability measures on Ωn satisfying
≤ min(pn(ω), qn(ω)) ≤ max(pn(ω), qn(ω)) ≤
for all ω in Ωn, where č and ĉ are fixed constants that are
independent of n. Observe that this requires the cardinality of
the alphabet size to grow linearly in n
≤ |Ωn| ≤
We observe two strings of length n. The first, denoted by x, is
a sequence of symbols drawn i.i.d. from Ωn according to pn.
The second, denoted by y, is a sequence of symbols drawn
i.i.d. from Ωn according to qn. We assume that x and y are
statistically independent. Note that both the alphabet and the
underlying probability measures are permitted to vary with n.
Note also that by assumption (1), each element of Ωn has
probability Θ(1/n) under both measures and thus will appear
Θ(1) times on average in both strings. In fact, the probability
of a given symbol appearing a fixed number of times in either
string is bounded away from 0 and 1 as n → ∞. In other
words, every letter is rare. The number of distinct symbols in
either string will grow linearly with n as a result.
Our focus shall be on the quantities pn(x) and pn(y). An
important initial observation to make is that the distributions
of these two random variables are invariant under a relabeling
of the elements of Ωn. It is therefore convenient to consider
the probabilities assigned by the measures pn and qn without
reference to the labeling of the symbols. It is also convenient
to normalize these probabilities so that they are Θ(1).
Let Pn denote the distribution of
(npn(xn), nqn(xn)),
where xn is drawn according to pn. Likewise, let Qn denote
the distribution of
(npn(yn), nqn(yn)),
where yn is drawn according to qn.
Note that both Pn and Qn are probability measures on C :=
[č, ĉ] × [č, ĉ]. It follows from the definitions that Pn and Qn
are absolutely continuous with respect to each other and the
Radon-Nikodym derivative is given by
(x, y) =
. (2)
Note that many quantities of interest involving pn and qn
can be computed using Pn (or Qn). For example, the entropy
of pn can be expressed as
dPn(x, y)
and the relative entropy between pn and qn is given by
D(pn||qn) =
dPn(x, y).
We shall assume that Pn converges in distribution to a
probability measure P on C. Since Pn and Qn are related
by (2), this implies that Qn converges to a distribution Q
satisfying
(x, y) =
III. PROBLEM FORMULATION
Recall that the classical (finite-alphabet, fixed-distribution)
asymptotic equipartition property (AEP) asserts that
logµ(w) = −H(µ) a.s., (3)
where w is an i.i.d. sequence drawn according to µ and H(·)
denotes discrete entropy. Loosely speaking, (3) says that the
probability of the observed sequence, µ(w), is approximately
exp(−nH(µ)).
In the rare events regime, on the other hand, one expects the
probability of an observed sequence to be approximately
for some constant h. Indeed, in the rare events regime the
following AEP holds true (all proofs are contained in Sec-
tion VII).
Theorem 1:
log(npn(xi)) =
log(x) dP (x, y) a.s.
Our goal is to estimate the limit in Theorem 1 universally,
that is, using only the observed sequence x without reference
to the probability measures pn. Of course, in the classical
setup, the analogous problem of universally estimating the
limit in (3) is straightforward. The distribution µ can be
determined from the observed sequence by the law of large
numbers, from which the entropy H(µ) can be calculated. In
the rare events regime, on the other hand, this approach fails
and the problem is more challenging.
We shall also study the following variation on this problem.
Consider the related quantity pn(y). That is, the sequence is
generated i.i.d. according to qn, but we evaluate its probability
under pn. This quantity arises in detection problems, where
one must determine the likelihood of a given realization under
multiple probability distributions. As in the single-sequence
setup, it turns out that this probability converges if it is suitably
normalized.
Theorem 2:
log(npn(yi)) =
log(x) dQ(x, y) a.s.
Our goal is then to estimate the limit in Theorem 2 using
only the observed sequences x and y. Again, in a fixed-
distribution setup, this problem is straightforward because the
two distributions can be determined exactly from the observed
sequences in the limit as n tends to infinity. In the rare events
regime, however, the problem is more challenging.
IV. THE GOOD-TURING ESTIMATOR
The Good-Turing estimator can be viewed as an estimator
for the probabilities of the individual symbols. Let Ak be the
set of symbols that appear k times in the sequence x, and
let ϕk = |Ak| denote the number of such symbols. The basic
form of the Good-Turing estimator assigns probability
(k + 1)ϕk+1
to each symbol that appears k ≤ n − 1 times [2]. The case
k = n must be handled separately, but this case is unimportant
to us because in the rare events regime the chance that only
one symbol appears in x is asymptotically negligible.
The Good-Turing formula can also be viewed as an estima-
tor for the total probability of all symbols that appear k times
in x, i.e., pn(Ak). In particular, the ϕk in the denominator can
be viewed as simply dividing the total probability
(k + 1)ϕk+1
equally among the ϕk symbols that appear k times. In previ-
ous work, we showed that the Good-Turing total probability
estimator is strongly consistent in that for any k ≥ 0,
(k + 1)ϕk+1
= lim
pn(Ak)
xke−x
dP (x, y) =: λk a.s. (5)
(see [6], where the notation is slightly different, for a proof
of a stronger version of this statement). The Good-Turing
probability estimator in (4) gives rise to a natural estimator
for the probability of the observed sequence x
(k + 1)ϕk+1
This in turn suggests the following estimator for the limit in
Theorem 1
(k + 1)ϕk+1
. (6)
This estimator is problematic, however, because for the largest
k for which ϕk > 0,
(k + 1)ϕk+1
which means that the kth term in (6) equals −∞. Various
“smoothing” techniques have been introduced to address re-
lated problems with the estimator [2]. Our approach will be
to truncate the summation at a large but fixed threshold, K
(k + 1)ϕk+1
In the rare events regime, with probability one it will eventu-
ally happen that ϕk > 0 for all k = 1, . . . ,K , thus obviating
the problem. By the result in (5), this estimator will converge
λk−1 log
. (7)
We next show that this quantity need not tend to the limit in
Theorem 1 as K tends to infinity.
Let Ωn be the set {1, 2, . . . , 3n}. Suppose that pn assigns
probability 1/(4n) to the first 2n elements and probability
1/(2n) to the remaining n. The distribution qn is obviously
not relevant here so we shall simply set it equal to pn.
The resulting distribution P will place mass 1/2 on each
of the points (1/4, 1/4) and (1/2, 1/2). From Theorem 1, the
limiting normalized probability of x is −(1/2) log 8. By (7),
the Good-Turing estimate converges to
e−1/4(1/4)k−1
(k − 1)!
1 + e−1/42k−1
8(1 + e−1/42k)
4(1 + e−1/42k−1)
e−1/4(1/4)k−1
(k − 1)!
1 + e−1/42k−1
Now as K tends to infinity, the second sum converges to the
correct answer, −(1/2) log 8. But one can verify that every
term in the first sum is strictly positive. Thus the Good-Turing
estimator is not consistent in this example.
The problem is that the Good-Turing estimator is estimating
the sum, or equivalently the arithmetic mean, of the probabil-
ities of the symbols appearing k times in x. Estimating the
sequence probability, on the other hand, amounts to estimating
the geometric mean of these probabilities. If pn assigns the
same probability to every symbol, then the arithmetic and geo-
metric means coincide, and one can show that the Good-Turing
sequence probability estimator is asymptotically correct. In the
above example, however, pn is not uniform, and the Good-
Turing formula converges to the wrong value. In the next
section, we describe an estimator that targets the geometric
mean of the probabilities instead of the arithmetic mean, and
thereby correctly estimates the sequence probability.
V. A BETTER GOOD-TURING ESTIMATOR
Write
ĉ+ č
and then let
γMk = −
(−c)−ℓ
(k + ℓ)!
m · k!
(k + ℓ+ 1)ϕk+ℓ+1
+ log(c)
(k + 1)ϕk+1
Note that γMk is only a function of x and in particular, it
does not depend on pn. The next theorem shows that for large
K and M ,
is a consistent estimator for the limit in Theorem 1.
Theorem 3: For any ǫ > 0,
log(npn(xi))−
≤ ǫ a.s. (8)
provided
exp(ĉ)c
ĉ− č
ĉ+ č
ĉK+1c
(K + 1)!
where
c = max(| log č|, | log ĉ|).
The idea behind Theorem 3 is this. Recall from (5) that
(k + 1)ϕk+1
xke−x
dP (x, y) a.s.
If one could find a sequence of constants ak such that
xke−x
= log(x)
on [č, ĉ], then one might expect that
(k + 1)ϕk+1
log(x) dP (x, y) a.s.
This is indeed the approach we took to find the formula for
γMk .
The estimator can be naturally extended to the two-sequence
setup, namely to the problem of universally estimating pn(y).
Let ϕk,ℓ be the number of symbols in Ωn that appear k
times in x and ℓ times in y. Then let
γ̃Mk = −
(−c)−ℓ
(k + ℓ)!
m · k!
jϕk+ℓ,j
+ log(c)
jϕk,j
Note that γ̃Mk is a function of x and y.
Theorem 4: For any ǫ > 0,
log(npn(yi))−
≤ ǫ a.s.
provided
exp(ĉ)c
ĉ− č
ĉ+ č
ĉK+1c
(K + 1)!
This result shows that although we are unable to determine
pn from x, we are able to glean enough information about pn
to determine the limit in Theorem 2.
VI. UNIVERSAL HYPOTHESIS TESTING
The γ̃Mk estimator leads to a natural scheme for the problem
of universal hypothesis testing. Suppose that we again observe
the sequences x and y, which we now view as training data. In
addition, we observe a test sequence, say z, which is generated
i.i.d. from the distribution rn. We assume that either rn = pn
for all n or rn = qn for all n. The problem is to determine
which of these two possibilities is in effect using only the
sequences x, y, and z.
Using Theorem 4, one can estimate pn(z) and qn(z), and
by comparing the two, determine which of the two distribu-
tions generated z. This will make for a consistent universal
classifier, without recourse to actually estimating the true
underlying distributions pn and qn. As a scheme for universal
hypothesis testing, however, this approach is quite complicated
and there is no reason to believe it would be optimal in
an error-exponent sense. We are currently investigating other,
more direct approaches to the universal hypothesis testing
problem in the rare events regime. For a discussion of universal
hypothesis testing in the traditional, fixed-distribution regime,
see Gutman [7] and Ziv [8].
VII. PROOFS
Due to space limitations, we will only prove Theorem 1
and sketch the proof of Theorem 3. The proofs of Theorems 2
and 4 are similar.
Lemma 1:
log(npn(xi))
log(x) dP (x, y).
Proof: Note that for any i
E[log(npn(xi))] =
pn(ω) log(npn(ω))
log(x) dPn(x, y).
Since log(x) is bounded and continuous over C and Pn
converges in distribution to P , the result follows.
Lemma 2:
log(npn(xi))
log(npn(xi))
= 0 a.s.
Proof: Consider the sum
log(npn(xi)).
If one symbol in the sequence x is altered, then this sum can
change by at most
It follows from the Azuma-Hoeffding-Bennett concentration
inequality [9, Corollary 2.4.14] that
log(npn(xi))
log(npn(xi))
≤ 2 exp
2(log(ĉ/č))2
The result then follows by the Borel-Cantelli lemma.
Note that Theorem 1 follows immediately from Lemmas 1
and 2.
The key step in the proof of Theorem 3 is showing that γMk
converges to the proper limit. This is shown in the next and
final lemma.
Lemma 3: For any ǫ > 0 and any k ≥ 0,
γMk −
log(x)
exp(−x)xk
dP (x, y)
≤ ǫĉ
a.s.,
provided
ĉ− č
ĉ+ č
Proof (sketch): Note that the limit exists by (5). By the
triangle inequality,
γMk −
log(x)
exp(−x)xk
dP (x, y)
∣γMk − γMk
γMk −
log(x)
exp(−x)xk
dP (x, y)
, (9)
where
γMk = −
(−c)−ℓ
(k + ℓ)!
m · k!
λk+ℓ + log(c)λk.
The first term on the right-hand side of (9) tends to zero by (5).
(−c)−ℓ
(k + ℓ)!
m · k!
exp(−x)xk
m · k!
(−c)−m
(−c)m−ℓ xℓ dP (x, y).
By the Binomial Theorem,
(−c)m−ℓ xℓ = (x− c)m.
Substituting these last two equations into (10) yields
γMk = −
)m exp(−x)xk
m · k!
dP (x, y)
+ log(c)λk.
Using the well-known power series
log(1 + x) =
(−1)m+1
valid for −1 < x ≤ 1, one can show that
č≤x≤ĉ
ĉ− č
ĉ+ č
by hypothesis. Thus
γMk −
log(x)
exp(−x)xk
dP (x, y)
)m exp(−x)xk
m · k!
dP (x, y)
) exp(−x)xk
dP (x, y)
exp(−x)xk
dP (x, y) ≤
Since
exp(−x)xk
one would expect from Lemma 3 that for large K and M ,
would be close to
log(x) dP (x, y).
Indeed, one can prove Theorem 3 using this approach. The
details are omitted.
REFERENCES
[1] A. Orlitsky and N. P. Santhanam, “Performance of universal codes over
infinite alphabets,” in Proc. IEEE Data Compression Conference, Mar.
2003, pp. 402–10.
[2] I. J. Good, “The population frequencies of species and the estimation of
population parameters,” Biometrika, vol. 40, no. 3/4, pp. 237–64, 1953.
[3] A. Orlitsky, N. P. Santhanam, and J. Zhang, “Always Good Turing:
Asymptotically optimal probability estimation,” Science, vol. 302, pp.
427–31, Oct. 2003.
[4] C. A. J. Klaassen and R. M. Mnatsakanov, “Consistent estimation of the
structural distribution function,” Scand. J. Statist., vol. 27, pp. 733–46,
2000.
[5] E. V. Khmaladze and R. Ya Chitashvili, “Statistical analysis of a large
number of rare events and related problems,” Proc. A. Razmadze Math.
Inst., vol. 92, pp. 196–245, 1989, in Russian.
[6] A. B. Wagner, P. Viswanath, and S. R. Kulkarni, “Strong consistency of
the Good-Turing estimator,” in IEEE Int. Symp. Inf. Theor. Proc., July
2006, pp. 2526–30.
[7] M. Gutman, “Asymptotically optimal classification for multiple tests with
empirically observed statistics,” IEEE Trans. Inf. Theory, vol. 35, no. 2,
pp. 401–8, Mar. 1989.
[8] J. Ziv, “On classification with empirically observed statistics and universal
data compression,” IEEE Trans. Inf. Theory, vol. 34, no. 2, pp. 278–86,
Mar. 1988.
[9] A. Dembo and O. Zeitouni, Large Deviations Techniques and Applica-
tions, 2nd ed. New York: Springer-Verlag, 1998.
	Introduction
	The Rare Events Regime
	Problem Formulation
	The Good-Turing Estimator
	A Better Good-Turing Estimator
	Universal Hypothesis Testing
	Proofs
	References
