论文标题
确定性有限内存偏置估计
Deterministic Finite-Memory Bias Estimation
论文作者
论文摘要
在本文中，我们考虑使用有限内存估算Bernoulli参数的问题。令$ x_1，x_2，\ ldots $为一系列独立分布的bernoulli随机变量，带有期望$θ$，其中$θ\ in [0,1] $。考虑使用$ s $状态的有限内存确定性机器，该机器在\ {1,2，\ ldots，s \} $中更新其状态$ m_n \ in \ in \ {1,2，\ ldots，s \} $，根据规则$ m_n = f（m_ {n-1}，x_n）$，其中$ f $是确定性的时间invariant varriant varriant varriant varriant varriant varriant varriant varriant varriant varriant varn。假设机器根据从状态空间到单位间隔的一些固定映射在每个时间点输出估计值。估计程序的质量是通过渐近风险来衡量的，这是瞬时二次风险的长期平均值。本文的主要贡献是任何此类机器可以达到的最小最严重的渐近风险的上限。这种界限与Leighton和Rivest衍生的下限相吻合，这意味着$θ（1/s）$是确定性$ s $ state机器的最小渐近风险。特别是，我们的结果反驳了长期以来的$θ（\ log s/s）$猜想，也是由Leighton和Rivest提出的。
In this paper we consider the problem of estimating a Bernoulli parameter using finite memory. Let $X_1,X_2,\ldots$ be a sequence of independent identically distributed Bernoulli random variables with expectation $θ$, where $θ\in [0,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 the machine outputs an estimate at each time point according to some fixed mapping from the state space to the unit interval. The quality of the estimation procedure is measured by the asymptotic risk, which is the long-term average of the instantaneous quadratic risk. The main contribution of this paper is an upper bound on the smallest worst-case asymptotic risk any such machine can attain. This bound coincides with a lower bound derived by Leighton and Rivest, to imply that $Θ(1/S)$ is the minimax asymptotic risk for deterministic $S$-state machines. In particular, our result disproves a longstanding $Θ(\log S/S)$ conjecture for this quantity, also posed by Leighton and Rivest.
