About

The balls in bins or balls and bins problem is one of the basic problems of computer science, with wide-ranging applications including hashing and load balancing. It asks: if $m$ balls are thrown at random into $n$ bins, then:

  • What is the probability that there is a bin with at least two balls?
  • What is the expected fraction of the bins that are nonempty?
  • What is the expected number of balls per nonempty bin?
  • What is the expected number of bins with more than one ball?

and so forth.

history | show excerpt | excerpt history