# Thread: probability of balls falling to bins

1. ## probability of balls falling to bins

Hi everyone, here is my question:

Suppose there are "b" balls and n bins, we like to put all balls into "n" bins and the probability that every ball falls into any bin is same(1/n).

Is there a simple equation/series of equations to calculate the probability that there are x bins (0<x<=n) with at least one ball in it?

I know this can be done by counting or permuting all possible outcomes but this is not feasible when b and n are large.

2. Number of ways to split b balls into n bins is:
$\binom{b+n-1}{b}$

Number of ways to split b balls into n bins with at least one ball in each bin:
$\binom{b - 1}{b - n}$

If you want to calculate exactly x bins filled, then this is easy
$\binom{n}{x}\binom{b - 1}{b - x}$
Why? Pick x bins and fill at least 1 balls in each bin.

If you want at least x bins filled, then it is probably easiest to do a summation:
$\sum_{k=x}^n \binom{n}{k}\binom{b-1}{b-k}$

3. Snowtea,

The difficulty with counting the number of ways to distribute the balls in the bins and using this to compute the probability is that not all distributions are equally likely. For example, suppose there are only 2 balls and 2 bins. The distributions 2-0 and 0-2 each occur with probability 1/4, but the probability of 1-1 is 1/2.

This problem is the Coupon Collector's Problem, slightly disguised. See, for example,

Coupon collector's problem - Wikipedia, the free encyclopedia

4. Originally Posted by awkward
Snowtea,

The difficulty with counting the number of ways to distribute the balls in the bins and using this to compute the probability is that not all distributions are equally likely. For example, suppose there are only 2 balls and 2 bins. The distributions 2-0 and 0-2 each occur with probability 1/4, but the probability of 1-1 is 1/2.

This problem is the Coupon Collector's Problem, slightly disguised. See, for example,

Coupon collector's problem - Wikipedia, the free encyclopedia
Hi awkward,

I have difficulty mapping the ball-bin problem to the coupon collector's problem. Could you please elaborate?

5. Suppose there are n different types of coupons, all equally likely, and you have b coupons. The problem you have posed is the same as determining the probability that you have x different types. Usually the question asked is if you have a complete set (x=n), so maybe this isn't exactly the classic Coupon Collector problem, but it's very close.