Accession Number:

ADA170229

Title:

Approximate Counting. A Martingale Approach.

Descriptive Note:

Interim rept. 15 May 85-14 May 86,

Corporate Author:

MASSACHUSETTS UNIV AMHERST DEPT OF MATHEMATICS AND STATISTICS

Personal Author(s):

Report Date:

1986-02-17

Pagination or Media Count:

14.0

Abstract:

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

Subject Categories:

  • Statistics and Probability

Distribution Statement:

APPROVED FOR PUBLIC RELEASE