
Accession Number : AD0721212
Title : Finite Memory Hypothesis Testing: Achieving Performance Bound without Randomization.
Descriptive Note : Final rept. 3 Apr 694 May 70,
Corporate Author : PHILCOFORD 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 finitestate 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