In many statistical problems, sample complexity, i.e. number of samples required to keep the error below a threshold, is quantity of central importance. In this talk, we will see an introduction to a slightly different model in which samples are plentiful, but the memory available to the computer is limited. Specifically, we will consider binary hypothesis testing under a limited memory framework, modeled via a finite automaton. We will define the concept of memory complexity, analogous to sample complexity, and show that the memory limited probability of error decays exponentially in the number of states of our automaton, similar to the exponential decay in the number of samples of the probability of error in the usual model.
Based on Hellman&Cover 1969.
