Statistical estimation with bounded memory

摘要

We investigate bounded-memory estimators of statistical functionals. It is shown that, for nondegenerate functionals and stochastic processes, it is impossible to achieve consistent estimation with bounded memory. In the positive direction, we show that O(log(l/e)) states suffice to achieve e-consistent estimation for a natural class of func-tionals. A canonical optimal construction is conjectured for arbitrary statistical functionals.