Finite memory hypothesis testing: Achieving performance bound without randomization
B. Chandrasekaran, Thomas J. Harley · 1970
Given a hypothesis testing problem about the bias of a coin for heads, H0 : p = P0 and H1 : p = p1, and a finite memory constraint, Cover and Hellman 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. The procedure requires randomization, whose memory requirements sometimes we may not be able to meet. 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.