# Technical Program

## Paper Detail

 Paper ID E.5.3 Paper Title Binary Hypothesis Testing with Deterministic Finite-Memory Decision Rules Authors Tomer Berg, Tel Aviv University, Israel; Or Ordentlich, Hebrew University, Israel; Ofer Shayevitz, Tel Aviv University, Israel Session E.5: Hypothesis Testing I Presentation Lecture Track Detection and Estimation Manuscript Click here to download the manuscript Virtual Presentation Click here to watch in the Virtual Symposium Abstract 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$.