Low complexity finite memory decision rules

By examining a particular hypothesis testing problem under a finite memory constraint we derive general guidelines for the design of asymptotically optimal, low complexity, finite memory decision rules. By asymptotically optimal we mean that only a fixed number of bits need be added to memory to achieve the optimal error probability. Thus the fraction of bits "lost" by these low complexity rules tends to zero as memory size becomes large. The rules developed are similar to quantized sequential probability ratio tests.