With a \(b\)-bit counter, we can ordinarily only count up to \(2^b - 1\). With R. Morris’s probabilistic counting, we can count up to a much larger value at the expense of some loss of precision.

We let a counter value of \(i\) represent a count of \(n_i\) for \(i = 0, 1, \dots, 2^{b-1}\), where the \(n_i\) form an increasing sequence of nonnegative values. We assume that the initial value of the counter is \(0\), representing a count of \(n_0 = 0\). The INCREMENT operation increases the counter by \(1\) with probability \(\frac{1}{n_{i+1} - n_i}\), and it leaves the counter unchanged with probability \(1-\frac{1}{n_{i+1}-n_i}\).

If we select \(n_i = i\) for all \(i \gt 0\), then the counter is an ordinary one. More interesting situations arise if we select, say, \(n_i = 2^{i-1}\) for \(i > 0\) or \(n_i = F_i\) (the \(i\)th Fibonacci number - see Section 3.2).

For this problem, assume that \(n_{2^{b}-1}\) is large enough that the probability of an overflow error is negligible.

a. Show that the expected value represented by the counter after \(n\) INCREMENT operations has been performed is exactly \(n\).

We know that the probability of the INCREMENT operation increasing the counter by \(1\) is \(\frac{1}{n_{i+1} - n_i}\). Suppose that our counter is currently at \(i\) and we perform the INCREMENT operation on it. If the operation does not change the counter, it will remain at the current value, \(n_i\). On the other hand, if the operation does change the counter it will be updated to \(n_i+1\). In other words, our expected increase is:

\[\frac{n_{i+1} - n_i}{n_{i+1} - n_i} = 1\text{.}\]

b. The analysis of the variance of the count represented by the counter depends on the sequence of the \(n_i\). Let us consider a simple case: \(n_i = 100i\) for all \(i \gt 0\). Estimate the variance in the value represented by the register after \(n\) INCREMENT operations have been performed.

For \(n_i = 100i\) we have that each INCREMENT operation changes the value of the counter with probability \(\frac{1}{100}\). Since this value is constant with respect to the current value of the counter, it can be considered a binomial distribution wherein the successful independent trial is represented by the counter value increasing. That is, \(p = 0.01\). Handily, the variance of a binomial distribution is \(np(1-p)\) and so our variance in this case is \(n \cdot 0.01 (1 - 0.01) = 0.0099n\). Finally, since each successful INCREMENT operation raises the count by 100, we need to account for this value in the variance and so our final answer is \(.99n\).