  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 $\theta$,
where $\theta \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 $\Theta(1/S)$ is the
minimax asymptotic risk for deterministic $S$-state machines. In particular,
our result disproves a longstanding $\Theta(\log S/S)$ conjecture for this
quantity, also posed by Leighton and Rivest.
