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: p=p sub 0 or H sub 1: p=p 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)