@Article{LR86,
  author = 	 { F. Thomson Leighton and Ronald L. Rivest },
  title = 	 { Estimating a Probability using Finite Memory },
  journal = 	 { IEEE Trans. on Information Theory },
  issn =         { 0018-9448 },                  
  OPTyear = 	 { 1986 },
  OPTmonth = 	 { November },
  date =         { 1986-11 },                  
  volume = 	 { IT-32 },
  number = 	 { 6 },
  pages = 	 { 733--742 },
  publisher =    { IEEE },
  doi =          { 10.1109/TIT.1986.1057250 },                 
  abstract =     {
        Let $\{X_i\}_{i=1}^{\infty}$ be a sequence of independent Bernoulli
        random variables with probability $p$ that $X_i=1$ and probability
        $q = 1 - p$ that $X_i = 0$ for all $i\ge 1$.  Time-invariant finite
        memory (i.e. finite-state) estimation procedures for the parameter
        $p$ are considered which take $X_1$, \cdots as an input sequence.
        In particular, an $n$-state deterministic estimation procedure is
        described which can estimate $p$ with mean-square error $O(\log n/n)$ and
        and $n$-state probabilistic estimation procedure which can estimate
        $p$ with mean-square error $O(1/n)$.  It is proved that the $O(1/n)$
        bound is optimal to within a constant factor.  In addition, it is shown
        that linear estimation procedures are just as powerful (up to the
        measure of mean-square error) as arbitrary estimation procedures.
        The proofs are based on an analog of the well-known matrix tree
        theorem that is called the Markov chain tree theorem.                  
                 },
}