Accession Number : AD0721212

Title :   Finite Memory Hypothesis Testing: Achieving Performance Bound without Randomization.

Descriptive Note : Final rept. 3 Apr 69-4 May 70,

Corporate Author : PHILCO-FORD CORP WILLOW GROVE PA COMMUNICATIONS AND TECHNICAL SERVICES DIV

Personal Author(s) : Chandrasekaran,B. ; Harley,Thomas J. , Jr

Report Date : FEB 1971

Pagination or Media Count : 18

Abstract : Given a hypothesis testing problem about the bias p of a coin for heads, H sub 0: p=p sub 0 or H sub 1: p=p sub 1, and a finite memory constraint, Hellman and Cover (1970) have derived a lower bound on the error probability achievable by finite-state machines, and they have also given a procedure which achieves this performance arbitrarily closely. This procedure requires randomization, whose memory requirements sometimes one may not be able to fulfill. This paper gives a procedure in which the expedient of a laboratory processing a large number of problems is used to achieve error probabilities close to the lower bound for each problem; in essence, the procedure employs the statistics of the problems themselves in a suitable way to simulate the randomizer. (Author)

Descriptors :   (*DECISION THEORY, PROBABILITY), LEARNING MACHINES, MATHEMATICAL LOGIC, PROBLEM SOLVING, INFORMATION THEORY, ARTIFICIAL INTELLIGENCE

Subject Categories : Operations Research

Distribution Statement : APPROVED FOR PUBLIC RELEASE