Binary Hypothesis Testing With Deterministic Finite-Memory Decision Rules

Jump to other IT Society Websites:

Binary Hypothesis Testing With Deterministic Finite-Memory Decision Rules


Creation Date: Jun 21, 2020

Published In: Jun 2020

Paper Type: Conference Paper

Book Title: Proceedings of the 2020 IEEE International Symposium on Information Theory

Address: Los Angeles, CA, USA


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


Award(s) Received:

COVID-19 Updates

Read important changes and updates to the 2020 activities of the IEEE Information Theory Society due to the COVID-19 pandemic at:


Table of Contents

IEEE TechNav