Finite Memory Hypothesis Testing: Achieving Performance Bound without Randomization.
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)
Document Details
- Document Type
- Technical Report
- Publication Date
- Feb 01, 1971
- Accession Number
- AD0721212
Entities
People
- B. Chandrasekaran
- Thomas J. Harley Jr.