- Free Articles
- Suffix Tree Construction in Hierarchical Memory Encyclopedia of Algorithms
- Probabilistic Data Forwarding in Wireless Sensor Networks Encyclopedia of Algorithms
- Renaming Encyclopedia of Algorithms
- Time in Philosophical Logic Encyclopedia of Database Systems
- Indoor Localization Encyclopedia of GIS
- More Free Articles
Tail Bounds for Occupancy Problems
Keywords and Synonyms
Balls and bins
Consider a random allocation of m balls to n bins where each ball is placed in a bin chosen uniformly and independently. The properties of the resulting distribution of balls among bins have been the subject of intensive study in the probability and statistics literature [3,4]. In computer science, this process arises naturally in randomized algorithms and probabilistic analysis. Of particular interest is the occupancy problem where the random variable under consideration is the number of empty bins.
In this entry a series of bounds are presented (reminiscent of the Chernoff bound for binomial distributions) on the tail of the distribution of the number of empty bins; the tail bounds are successively tighter, but each new bound has a more complex closed form. Such strong bounds do not seem to have appeared in the earlier literature.
The following notation in presenting sharp