# probability of balls falling to bins

Printable View

• January 10th 2011, 10:36 PM
asura
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.

Please advise.
• January 11th 2011, 08:59 AM
snowtea
Number of ways to split b balls into n bins is:
$\binom{b+n-1}{b}$
Why? Think about this diagram ***|**||*** for dividing 8 balls into 4 bins as (3,2,0,3)

Number of ways to split b balls into n bins with at least one ball in each bin:
$\binom{b - 1}{b - n}$
Why? Think about this diagram o*|o**|o*|o** for dividing 10 balls into 4 bins as (2,3,2,3)

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}$
• January 11th 2011, 05:50 PM
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
• January 20th 2011, 06:14 AM
asura
Quote:

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?
• January 20th 2011, 02:02 PM
awkward
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.