论文标题
二进制假设测试具有确定性有限内存决策规则
Binary Hypothesis Testing with Deterministic Finite-Memory Decision Rules
论文作者
论文摘要
在本文中，我们考虑了使用有限记忆系统进行二元假设检验的问题。令$ x_1，x_2，\ ldots $为一系列独立分布的bernoulli随机变量，预期$ p $属于$ \ mathcal {h} _0 $ _0 $和$ q $，而$ q $ yno $ \ mathcal {H} _1 _1 $。考虑使用$ s $状态的有限内存确定性机器，该机器在\ {1,2，\ ldots，s \} $中更新其状态$ m_n \ in \ {1,2，\ ldots，s \} $，根据规则$ $ m_n = f（m_ {n-1}，x_n）$，其中$ f $是确定性的时间范围的函数。假设我们让该过程运行很长时间（$ n \ rightarrow \ infty）$，然后根据从状态空间到假设空间的一些映射做出决定。本文的主要贡献是任何此类机器的贝叶斯错误概率$ p_e $的下限。特别是，我们的发现表明，确定性机器的最大指数衰减率与$ s $的最大指数衰减率与$ s $，而对于随机机器，可以无限制地依靠Hellman的结果。
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$ and $q$ under $\mathcal{H}_1$. Consider a finite-memory deterministic machine with $S$ states that updates its state $M_n \in \{1,2,\ldots,S\}$ at each time 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. The main contribution of this paper is a lower bound on the Bayes error probability $P_e$ of any such machine. In particular, our findings show that the ratio between the maximal exponential decay rate of $P_e$ with $S$ for a deterministic machine and for a randomized one, can become unbounded, complementing a result by Hellman.
