Approximate counting: A detailed analysis

Reviewer: William J. J. Rey

What is counting__?__ As we know, it consists in going from 0 to 1, from 1 to 2, and so forth; an increment of 1 is made at each step. But there are other possibilities; approximate counting consists of applying the increment with a probability p and no increment with probability 1? p. The counter state c exhibits a logarithmic characteristics, while p=exp(? ac). Analyzing this Markov process (formally, a discrete time pure birth process), the paper goes through a good piece of mathematics to derive with precision the expected value and variance of the counter state after n steps. It is good and interesting, although I wonder whether all minor technicalities had to be reported; rather, I would have appreciated a treatment less dedicated to the fact that p is exponential. “Approximate counting appears as the method of choice when a fairly constant relative accuracy is needed over a large range of values.”