Optimal deterministic algorithm for the simple symmetric hypotheses testing problem
View/Open
Author
Chodchoey, Boorapa
Date
1974Advisor
Shubert, Bruno
Second Reader
Wong, Peter
Metadata
Show full item recordAbstract
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
2nvalued 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
,nl
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) .
Description
Approved for public release; distribution in unlimited.
Collections
Related items
Showing items related by title, author, creator and subject.

Dynamic Characteristics of Liquid Motion in Partially Filled Tanks of a Spinning Spacecraft
Agrawal, B.N. (1993);This paper presents a boundarylayer model to predict dynamic characteristics of liquid motion in partially filled tanks of a spinning spacecraft. The solution is obtained by solving three boundaryvalue problems: an ... 
Numerically solving a transient heat conduction problem with convection and radiation
Albert, David J. (Monterey, California. Naval Postgraduate School, 199306);The transient surface temperature distribution is determined for the flat plate and sphere subjected to cooling by combined convection and radiation. In the study, the initial boundary value problem is reduced to a singular ... 
Some remarks on the finitememory Khypotheses problems
Shubert, Bruno O. (Monterey, California. Naval Postgraduate School, 197410); NPS55Sy74101Finitememory statistical problems typically deal with the situation where the class of statistics is restricted to those taking on a fixed finite number of values. Although a potentially infinite number of samples may be ...