Convergence properties of functional estimates for discrete distributions

Abstract Suppose P is an arbitrary discrete distribution on acountable alphabet 𝒳. Given an i.i.d. sample ( X 1 ,…, X n ) drawnfrom 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 & Sons, Inc. Random Struct. Alg., 19: 163–193, 2001