Approximate Counting. A Martingale Approach.

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)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Feb 17, 1986
Accession Number
ADA170229

Entities

People

  • Walter A. Rosenkrantz

Organizations

  • University of Massachusetts Amherst

Tags

Communities of Interest

  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Air Force
  • Air Force Facilities
  • Algorithms
  • Complex Variables
  • Inequalities
  • Markov Chains
  • Mathematical Analysis
  • Mathematics
  • Probability
  • Probability Distributions
  • Random Variables
  • Security
  • Statistical Algorithms
  • Statistics

Fields of Study

  • Mathematics

Readers

  • Mathematical Modeling and Probability Theory.
  • Sensor Fusion and Tracking Systems.