Detection and Estimation
Hypothesis Testing I

Binary Hypothesis Testing with Deterministic Finite-Memory Decision Rules

Tomer Berg, Or Ordentlich, Ofer Shayevitz

Date & Time

01:00 am – 01:00 am


In this paper we consider the problem of binary hypothesis testing with finite memory systems. Let $X_1,X_2,\ldots$ be a sequence of independent identically distributed Bernoulli random variables, with expectation $p$ under $\mathcal{H}_0$ or $q$ under $\mathcal{H}_1$. Consider a finite-memory deterministic machine with $S$ states, where at each time point the machine's state $M_n \in \{1,2,\ldots,S\}$ is updated according to the rule $M_n = f(M_{n-1},X_n)$, where $f$ is a deterministic time-invariant function. Assume that we let the process run for a very long time ($n\rightarrow \infty)$, and then make our decision according to some mapping from the state space to the hypothesis space. Our main contribution in the paper is a lower bound on the probability of error of any such machine. Our bound is asymptotically tight and reveals that deterministic machines are significantly inferior to random machines when either one of the biases approaches $1$ or $0$.


Tomer Berg

Tel Aviv University

Or Ordentlich

Hebrew University of Jerusalem

Ofer Shayevitz

Tel Aviv University

Session Chair

Narayana Santhanam

University of Hawaii at Manoa