Optimal deterministic algorithm for the simple symmetric hypotheses testing problem
Boorapa Chodchoey · Calhoun: The Naval Postgraduate School Institutional Archive (Naval Postgraduate School) · 1974
This paper introduces a class of finite -memory deterministic algorithms for the following problem of hypotheses testing under a finite memory constraint. Let X 1 ,X-,X_,... be a sequence of independent, identically distributed Bernoulli random variables where X. can take on values H or T. The problem is to decide between the two simple hypothesis H : P(X i =H) = p vs. T : P(X.=H) = q, where P(# is true) = tt = P(T is true) = tt.. = h. The X.'s are observed sequentially and a new decision must be formulated after each observation. Let the data be summarized after each new observation by a 2n-valued statistic VeS = {1, , 2, , . . . ,n, ,n , (n- 1) , . . . , 2 , 1 } , which is updated according to the rule V\ = f (V,.. ,X,) , where f : S X (H,T)-*S; is the transition function. Let the decision rule take action [ H is true if V,e (1, , 2, , . . . ,n, ) d(v k ) J [r is true if V k e(n t ,n-l t ,. .. ,2 t ,l t ) , at time k. The objective is to find the function f which minimizes the probability of error P(e) = tt P(d = T\H is true) + tt P(d = H\T is true). The algorithm may be taught of as a finite state automaton, in which the inputs are the observations, the outputs are the decisions, and the states constitute the memory. In this paper, the optimal algorithms are found for a small number of states (up to 20) .