Balls, Bins, and Random Graphs
Lists
Only you see this
Abstract
In this chapter, we focus on one of the most basic of random processes: m balls are thrown randomly into n bins, each ball landing in a bin chosen independently and uniformly at random. We use the techniques we have developed previously to analyze this process and develop a new approach based on what is known as the Poisson approximation. We demonstrate several applications of this model, including a more sophisticated analysis of the coupon collector's problem and an analysis of the Bloom filter data structure. After introducing a closely related model of random graphs, we show an efficient algorithm for finding a Hamiltonian cycle on a random graph with sufficiently many edges. Even though finding a Hamiltonian cycle is NP-hard in general, our result shows that, for a randomly chosen graph, the problem is solvable in polynomial time with high probability.
BibTeX
@inproceedings{mitzenmacher2005balls,
author = {Michael Mitzenmacher and Eli Upfal},
title = {{Balls, Bins, and Random Graphs}},
booktitle = {Cambridge},
year = {2005},
doi = {10.1017/cbo9780511813603.006},
}Loading related content...