2020 IEEE International Symposium
on Information Theory
21-26 June 2020 • Los Angeles, California, USA
| 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$. | ||
Plan Ahead
2021 IEEE International Symposium on Information Theory
11-16 July 2021 | Melbourne, Victoria, Australia
