5-1 Probabilstic 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 that a count of $n_i$ for $i = 0, 1, \ldots, 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 $\text{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 $\text{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 \ge 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$ $\text{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 \ge 0$. Estimate the variance in the value represented by the register after $n$ $\text{INCREMENT}$ operations have been performed.

a. To show that the expected value represented by the counter after $n$ $\text{INCREMENT}$ operations have been performed is exactly $n$, we can show that each expected increment represented by the counter is $1$.

Assume the initial value of the counter is $i$, increasing the number represented from $n_i$ to $n_{i + 1}$ is with a probability of $\frac{1}{n_{i + 1} - n_i}$ and leaving the value not changed otherwise.

The expected increase:

$$ \frac{n_{i + 1} - n_i}{n_{i + 1} - n_i} = 1. $$

b. For this choice of $n_i$ , we have that at each increment operation, the probability that we change the value of the counter is $\frac{1}{100}$. Since this is a constant with respect to the current value of the counter $i$, we can view the final result as a binomial distribution with a $p$ value of $0.01$. Since the variance of the counter value $C_n$ is given by the formula for a binomial distribution:

$$ \text{Var}(C_n) = np(1-p) = n \cdot 0.01 \cdot (1 - 0.01) = 0.0099n. $$

The question asks for the variance of the value represented by the counter, let's call it $V_n$. The relationship is $V_n = 100 \cdot C_n$.

Using the variance property $\text{Var}(aX) = a^2\text{Var}(X)$, we get:

$$ \text{Var}(V_n) = \text{Var}(100 \cdot C_n) = 100^2 \cdot \text{Var}(C_n) = 10000 \cdot (0.0099n) = 99n. $$

So, the variance is going to be equal to $99n$.