Memory Complexity of Estimating Entropy and Mutual Information

We observe an infinite sequence of independent identically distributed random variables X-1, X-2,& mldr; drawn from an unknown distribution p over [n] , and our goal is to estimate the entropy H(p) = -E[logp(X)] within an epsilon -additive error. To that end, at each time point we are allowed to update a finite-state machine with S states, using a possibly randomized but time-invariant rule, where each state of the machine is assigned an entropy estimate. Our goal is to characterize the minimax memory complexity S & lowast; of this problem, which is the minimal number of states for which the estimation task is feasible with probability at least 1 - delta asymptotically, uniformly in p. Specifically, we show that there exist universal constants C-1 and C-2 such that S* <= C-1 & sdot;n(log n)(4)/epsilon(2)delta for epsilon not too small, and S* >= C-2 & sdot;max{n, log n/epsilon} for epsilon not too large. The upper bound is proved using approximate counting to estimate the logarithm of p, and a finite memory bias estimation machine to estimate the expectation operation. The lower bound is proved via a reduction of entropy estimation to uniformity testing. We also apply these results to derive bounds on the memory complexity of mutual information estimation.