We have m balls that are thrown into n bins, with the location of each ball chosen independently and uniformly at random from n possibilities. | LECTURE 6 BINS AND BALLS APPLICATIONS HASHING BLOOM FILTERS 2010 Van Nguyen Probability for Computing Agenda Review the problem of bins and balls Poisson distribution Hashing Bloom Filters 2010 Van Nguyen Probability for Computing 2 Balls into Bins We have m balls that are thrown into n bins with the location of each ball chosen independently and uniformly at random from n possibilities. What does the distribution of the balls into the bins look like Birthday paradox question is there a bin with at least 2 balls How many of the bins are empty How many balls are in the fullest bin Answers to these questions give solutions to many problems in the design and analysis of algorithms 2010 Van Nguyen Probability for Computing
