Convergence properties of functional estimates for discrete distributions

Suppose P is an arbitrary discrete distribution on a countable alphabet script X. Given an i.i.d. sample (X1 , . . . , Xn) drawn from P, we consider the problem of estimating the entropy H(P) or some other functional F = F(P) of the unknown distribution P. We show that, for additive functionals satisfying mild conditions (including the cases of the mean, the entropy, and mutual information), the plug-in estimates of F are universally consistent. We also prove that, without further assumptions, no rate-of-convergence results can be obtained for any sequence of estimators. In the case of entropy estimation, under a variety of different assumptions, we get rate-of-convergence results for the plug-in estimate and for a nonparametric estimator based on match-lengths. The behavior of the variance and the expected error of the plug-in estimate is shown to be in sharp contrast to the finite-alphabet case. A number of other important examples of functionals are also treated in some detail. © 2001 John Wiley & Suns, Inc