Assume there are balls and bins. We denote the event that ball falls into bin , and denote the event that balls and collide.
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