Learning with Finite Memory

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^ = inf(f,d)Pₑ(f, d). Let the a.e. maximum and minimum likelihood ratios be defined by l̄ = (P₀(A)/P₁(A)) and l = inf(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(π₀π₁γᵐ⁻¹)1/2 - 1/(γᵐ⁻¹ - 1), under the nondegeneracy condition γᵐ⁻¹ max\π₀/π₁, π₁/π₀\; 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.