Approximate counting:a martingale approach
Walter A. Rosenkrantz · Stochastics · 1987
Approximate counting is a probabilistic algorithm for keeping track of large numbers of events by means of a counter of limited range. In this paper we present an analysis of this algorithm using the elementary theory of martingales. The methods are also applicable to the analysis of the counter which occurs in the exponential back off protocol