5-1 Probabilistic counting

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,...,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 works on a counter containing the value $i$ in a probabilistic manner. If $i=2^{b}-1$, then the operation reports an overflow error. Otherwise, the INCREMENT operation increases the counter by $1$ with probability $1/(n_{i+1}-n_{i})$, and it leaves the counter unchanged with probability $1-1/(n_{i+1}-n_{i})$.

If we select $n_{i}=i$ for all $i \geq 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 equation (3.31) on page 69).

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 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\geq 0$. Estimate the variance in the value represented by the register after $n$ INCREMENT operations have been performed.

a

Let $I_i$ be the value incresed in the $i$th INCREMENT operations, $V$ be the value represented by the counter.

$$ \begin{aligned} I_i & = \begin{cases} n_{j+1}-n_{j} & \text{ with probablity of } \frac{1}{n_{j+1}-n_{j}}\cr 0 & \text{ with probablity of } 1-\frac{1}{n_{j+1}-n_{j}} \end{cases}\cr E[V] & = E\left[\sum_{i=1}^{n} I_i\right]\cr & = \sum_{i=1}^{n} E[I_i]\cr & = \sum_{i=1}^{n} 1\cr & = n\cr \end{aligned} $$

b

$$ \begin{aligned} Pr(V=100i) & = {n\choose i}p^i(1-p)^{n-i}\quad i=0,1,2,3..,n\cr V/100 & \text{ satisfies binomial distribution}\cr D[V] & = 10000np(1-p)\cr & = 99n\cr \end{aligned} $$