2024/06/10 by Berg, Tomer, Ordentlich, Or, Shayevitz, Ofer
#FOS: Computer and information sciences #Information Theory (cs.IT)
paper · doi:10.48550/arxiv.2406.06312
We observe an infinite sequence of independent identically distributed random variables X1,X2,… drawn from an unknown distribution p over [n], and our goal is to estimate the entropy H(p)=-𝔼[log p(X)] within an ε-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^* of this problem, which is the minimal number of states for which the estimation task is feasible with probability at least 1-δ asymptotically, uniformly in p. Specifically, we show that there exist universal constants C1 and C2 such that S^* ≤ C1⋅(n (log n)4)/(ε2δ) for ε not too small, and S^* ≥ C2 ⋅ max \n, (log n)/(ε)\ for ε 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.