Approximate Counting. A Martingale Approach.
Interim rept. 15 May 85-14 May 86,
MASSACHUSETTS UNIV AMHERST DEPT OF MATHEMATICS AND STATISTICS
Pagination or Media Count:
Approximate counting is a probabilistic algorithm for keeping track to large numbers of events by means of counters 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. Author
- Statistics and Probability