Memory Complexity of Estimating Entropy and Mutual Information
Tomer Berg, Or Ordentlich, Ofer Shayevitz · IEEE Transactions on Information Theory · 2025
We observe an infinite sequence of independent identically distributed random variables$X_{1},X_{2},\ldots $drawn from an unknown distributionpover$[n]$, and our goal is to estimate the entropy$H(p)=-\mathop {\mathrm {\mathbb {E}}} olimits [\log p(X)]$within an$\varepsilon $-additive error. To that end, at each time point we are allowed to update a finite-state machine withSstates, 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^{*}$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 inp. Specifically, we show that there exist universal constants$C_{1}$and$C_{2}$such that$ S^{*} \leq C_{1}\cdot \frac {n (\log n)^{4}}{\varepsilon ^{2}\delta }$for$\varepsilon $not too small, and$S^{*} \geq C_{2} \cdot \max \left \{{{n, \frac {\log n}{\varepsilon }}}\right \}$for$\varepsilon $not too large. The upper bound is proved using approximate counting to estimate the logarithm ofp, 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.