Key points are not available for this paper at this time.
This paper develops the theory of the design and performance of optimal finite-memory systems for the two-hypothesis testing problem. Let X₁, X₂, be a sequence of independent identically distributed random variables drawn according to a probability measure P. Consider the standard two-hypothesis testing problem with probability of error loss criterion in which P = P₀ with probability ₀; and P = P₁ with probability ₁. Let the data be summarized after each new observation by an m-valued statistic T\ 1, 2, , m\ which is updated according to the rule Tₙ = f (T₍-₁, Xₙ), where f is a (perhaps randomized) time-invariant function. Let d: \ 1, 2, , m\ \ H₀, H₁\ be a fixed decision function taking action d (Tₙ) at time n, and let Pₑ (f, d) be the long-run probability of error of the algorithm (f, d) as the number of trials n. Define P^ = (₅, ₃) Pₑ (f, d). Let the a. e. maximum and minimum likelihood ratios be defined by l = (P₀ (A) /P₁ (A) ) and l = (P₀ (A) /P₁ (A) ) where the supremum and infimum are taken over all measurable sets A for which P₀ (A) + P₁ (A) > 0. Define = l/l. It will be shown that P^ = 2 (₀₁^m-1) ^1{2} - 1/ (^m-1 - 1), under the nondegeneracy condition ^m-1 \₀/₁, ₁/₀\; and a simple family of -optimal (f, d) 's will be exhibited. In general, an optimal (f, d) does not exist; and -optimal algorithms involve randomization in f.
Hellman et al. (Mon,) studied this question.