In this talk, we will consider the problem of binary hypothesis testing with finite memory. Consider a sequence of IID random variables with expectation p under hypothesis H_0 and q under hypothesis H_1. Consider a finite-state machine with state M_n at time n. Let the state of the system be governed by the rule M_n = f(M_{n-1},X_n) where f is a deterministic time-invariant function. Assume that we let this process run for a very long time and then make a decision according to some mapping from the state space to the hypothesis space. We will bound the error probability of any hypothesis testing system.
