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 = 0
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 = 0;
  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+1 \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}-1$ is an unbiased estimator of the number $n$ .

Proof

Notice that $2^{C_0} = 1$ . 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+1$ .

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+1)~. \end{gather*}$ From this we easilly get $E[4^{C_n}] = \frac{1}{2}(3 n^2+3 n + 2)$ , so $\mathrm{var}(2^{C_n}) = E[4^{C_n}] - (E[2^{C_n}])^2 = \frac12 n(n-1)$ .

$\square$

P. Flajolet in paper Approximate Counting: A Detailed Analysis (BIT 25, (1985), 113-134) showed that

$E[C_n] = \log_2(n) - c + \omega(\log_2(n)) + O(n^{-0.98})$ for some constant

$c\approx 0.273954$ and

$\omega$ is a periodic function with period

$1$ such that

$|\omega(x)|\lt 10^{-5}$ for each

$x$ .