Finite Memory Hypothesis Testing: Achieving Performance Bound without Randomization.

Given a hypothesis testing problem about the bias p of a coin for heads, H sub 0 pp sub 0 or H sub 1 pp sub 1, and a finite memory constraint, Hellman and Cover 1970 have derived a lower bound on the error probability achievable by finite-state machines, and they have also given a procedure which achieves this performance arbitrarily closely. This procedure requires randomization, whose memory requirements sometimes one may not be able to fulfill. This paper gives a procedure in which the expedient of a laboratory processing a large number of problems is used to achieve error probabilities close to the lower bound for each problem in essence, the procedure employs the statistics of the problems themselves in a suitable way to simulate the randomizer. Author