Entropy Estimators with Almost Sure Convergence and an O(n-1) Variance

The problem of the estimation of the entropy rate of a stationary ergodic process mu is considered. A new nonparametric entropy rate estimator is constructed for a sample of n sequences (X₁ ⁽¹⁾,...,X_m ⁽¹⁾ ),..., (X_n ⁽¹⁾ ,....,X_m ⁽ⁿ⁾) independently generated by mu. It is shown that, for m = O(log n), the estimator converges almost surely and its variance is upper-bounded by O(n^-1) for a large class of stationary ergodic processes with a finite state space. As the order O(n^-1) of the variance growth on n is the same as that of the optimal Cramer-Rao lower bound, presented is the first near-optimal estimator in the sense of the variance convergence.