It is known that a processor with limited memory consisting of an $m$-state machine can distinguish two coins with biases that differ by $1/m$. On the other hand, the best additive accuracy with which the same processor can estimate the bias of a coin is only $1/sqrt{m}$. We demystify this apparent shrinkage in memory by showing that for any such estimator using an $m$-state machine, there exist two values of the bias that are $1/sqrt{m}$ apart but for which the effective number of states available to resolve them is only $O(sqrt{m})$. Building on this result, we show that the number of bits of memory required to estimate a bias in the interval $(a, a2^alpha)$ with a multiplicative accuracy of $2^{pm delta}$ is $log(alpha/delta^2)$, up to an additive constant. In fact, we show that the lower bound is attained by a Gaussian counter, namely a probabilistic counter whose stationary distribution has a Gaussian form. This gives a precise characterization of
memory-complexity of bias estimation along with a heuristically appealing family of optimal estimators. Underlying our results are new bounds for estimation of location parameter of a discrete exponential family, which maybe of independent interest.