Finite Memory Algorithms for Testing Bernoulli Random Variables.

摘要

This paper solves the basic multiple hypothesis-testing problem with a time-varying finite-state automaton. Let X1,X2,..., be a sequence of iid Bernoulli random variables with unknown parameter p = Pr(Xi = 1). The K-hypothesis testing problem is investigated under the following assumptions: the Xi's are observed sequentially, and summarized after each new observation by an m-valued statistic T sub n a member of which is updated by an algorithm of the form T sub n = f sub n(T(n-1),X(n)). Two automata are exhibited which make only a finite number of errors with probability one: M(1), a 2K-state machine resolving perfectly the K simple hypothesis H(k):p = p sub k(k = 1,...,K); and M2, a 4-state machine solving the difficult testing problem H(0):p = p(0) versus H(1):p not equal p(0). The algorithms do not require artificial randomization. The rate of convergence is related to the Kullback discrimination information between the hypotheses. (Author)