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:

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 a binomial distribution is \(np(1 − p)\), and we have that each success is worth \(100\) instead, the variance is going to be equal to \(0.99n\).

本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用