Memory Complexity of Estimating Entropy and Mutual Information

Tomer Berg, Or Ordentlich, Ofer Shayevitz

We observe an infinite sequence of independent identically distributed random variables $X_1,X_2,\dots$ drawn from an unknown distribution $p$ over $[n]$, and our goal is to estim…