Technical Program

Paper Detail

Paper IDE.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$.

Plan Ahead


2021 IEEE International Symposium on Information Theory

11-16 July 2021 | Melbourne, Victoria, Australia

Visit Website!