Assume there are balls and bins. We denote the event that ball falls into bin , and denote the event that balls and collide.

Collision probability

Probability of any two particular balls collide:

Expected number of collision after tossing balls: Define indicator function . Then the number of collisions is . The expected number of collision is therefore:

Probability of no collision at all:

Number of balls to throw to expect a collision: Solve for in


Probability of a particular bin is empty:

Probability that a particular bin has exactly balls:

which the bound is obtained by the inequality .

Probability that a bin has at least balls:

By considering only balls out of and ignoring the others, we have the probability upperbounded by