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 i represent a count of n(i) for i = 0, 1, . . . , 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 n0 = 0. The Increment operation works on a counter containing the value i in a probabilistic manner. If i = 2^b?1, then the operator reports an overflow error. Otherwise, the Increment operator increases the counter by 1 with probabilities 1/(n(i+1) ? n(i)), and it remains unchanged with probability 1 ? 1/(n(i+1) ? n(i)).

If we select n(i) = i for all i ? 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 ith Fibonacci number—See Section 3.2 in the text).

For this problem, assume that n(2^b?1) is large enough that the probability of an overflow error is negligible.

(a) Prove that the expected value represented by the counter after n Increment operations have been performed is exactly n.

(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 ? 0. Determine the variance in the value represented by the register after n Increment operations have been performed.