Binary Hypothesis Testing with Deterministic Finite-Memory Decision Rules
Tomer Berg, Or Ordentlich, Ofer Shayevitz · 2020
In this paper we consider the problem of binary hypothesis testing with finite memory systems. Let X1, X2, .. . be a sequence of independent identically distributed Bernoulli random variables, with expectation p under H0and q under H1. Consider a finite-memory deterministic machine with S states that updates its state Mn∈ {1, 2, ... , S} at each time according to the rule Mn= f(Mn-1, Xn), where f is a deterministic time-invariant function. Assume that we let the process run for a very long time (n → ∞), and then make our decision according to some mapping from the state space to the hypothesis space. The main contribution of this paper is a lower bound on the Bayes error probability Peof any such machine. In particular, our findings show that the ratio between the maximal exponential decay rate of Pewith S for a deterministic machine and for a randomized one, can become unbounded, complementing a result by Hellman.