We investigate the existence of bounded-memory consistent estimators of various statistical functionals. This question is resolved in the negative in a rather strong sense. We propose various bounded-memory approximations, using techniques from autom
ata theory and stochastic processes. Some questions of potential interest are raised for future work.
We give a universal kernel that renders all the regular languages linearly separable. We are not able to compute this kernel efficiently and conjecture that it is intractable, but we do have an efficient $eps$-approximation.
The rate at which dependencies between future and past observations decay in a random process may be quantified in terms of mixing coefficients. The latter in turn appear in strong laws of large numbers and concentration of measure results for depend
ent random variables. Questions regarding what rates are possible for various notions of mixing have been posed since the 1960s, and have important implications for some open problems in the theory of strong mixing conditions. This paper deals with $eta$-mixing, a notion defined in [Kontorovich and Ramanan], which is closely related to $phi$-mixing. We show that there exist measures on finite sequences with essentially arbitrary $eta$-mixing coefficients, as well as processes with arbitrarily slow mixing rates.
