Morris Probabilistic Counter
Published by Robert Morris from Bell Laboratories in Counting Large Numbers of Events in Small Registers in Communications of the ACM vol. 21, 10 (1977), 840–842.
Algorithm
Psedo-code
INITIALLY: C = 1 INCREMENT: If (random() <= 2-C) C = C + 1
In words: when incrementing the value C, "flip a coin" C times. If you get "Heads" each time, then increment C. Otherwise, do nothing.
Code in Scala
class MC() {
var C = 1;
val r = scala.util.Random
def Inc() : Unit = {
if (r.nextDouble < math.pow(2,-C)) C = C + 1
}
def getC():Int = {C}
def getE():Double = {math.pow(2,C) - 2.0}
}
Theorem
Let $C_n$ be the value stored in Morris Counter after $n$ increments. Then
$$ \mathrm{E}[2^{C_n}] = n+2 \quad and \quad \mathrm{var}(2^{C_n}) = \frac12 n(n+1) ~. $$From this theorem we deduce that the random variable $R = 2^{C_n}-2$ is an unbiased estimator of the number $n$.
Proof
It is clear that $2^{C_0} = 2$. Next we have $$ \begin{gather*} E[2^{C_{n+1}}] = \sum_k 2^k \Pr[C_{n+1}=k] = \\ \sum_k 2^k \Pr[C_{n+1}=k|C_n=k]\Pr[C_n=k] + \sum_k 2^k \Pr[C_{n+1}=k|C_n=k-1]\Pr[C_n=k-1] = \\ \sum_k 2^k \left(1- \left(\frac12\right)^k\right) \Pr[C_n=k] + \sum_k 2^k \left(\frac12\right)^{k-1}\Pr[C_n=k-1] = \\ (E[2^{C_n}] - 1) + 2\cdot 1 = E[2^{C_n}]+1~. \end{gather*} $$ Therefore $E[2^{C_n}] = n+2$.
The computation of the variance is slightly longer. First we compute $E[(2^{C_{n+1}})^2]$: $$ \begin{gather*} E[4^{C_{n+1}}] = \sum_k 4^k \Pr[C_{n+1}=k] = \\ \sum_k 4^k \Pr[C_{n+1}=k|C_n=k]\Pr[C_n=k] + \sum_k 4^k \Pr[C_{n+1}=k|C_n=k-1]\Pr[C_n=k-1] = \\ \sum_k 4^k \left(1- \left(\frac12\right)^k\right) \Pr[C_n=k] + \sum_k 4^k \left(\frac12\right)^{k-1}\Pr[C_n=k-1] = \\ (E[4^{C_n}] - E[2^{C_n}]) + 4\cdot E[2^{C_n}]) = E[4^{C_n}]+ 3 E[2^{C_n}] = \\ E[4^{C_n}]+ 3(n+2)~. \end{gather*} $$ From this we easilly get $E[4^{C_n}] = \frac{1}{2}(3 n^2+9 n+8)$, so $var(2^{C_n}) = E[4^{C_n}] - (E[2^{C_n}])^2 = \frac12 n(n+1)$.
$\square$