Results 1 to 5 of 5

Math Help - probability of balls falling to bins

  1. #1
    Newbie
    Joined
    Jan 2011
    Posts
    2

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Dec 2010
    Posts
    470
    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}
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1
    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
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Jan 2011
    Posts
    2
    Quote Originally Posted by awkward View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Probability on balls
    Posted in the Statistics Forum
    Replies: 3
    Last Post: January 6th 2011, 05:56 PM
  2. a basket contains 5 red balls, 3 blue balls, 1 green balls
    Posted in the Advanced Statistics Forum
    Replies: 3
    Last Post: May 28th 2010, 03:39 AM
  3. probability of balls
    Posted in the Statistics Forum
    Replies: 0
    Last Post: December 6th 2009, 08:08 PM
  4. Probability - balls in baskets
    Posted in the Advanced Statistics Forum
    Replies: 1
    Last Post: February 18th 2009, 02:57 AM
  5. Replies: 3
    Last Post: February 19th 2008, 12:12 PM

Search Tags


/mathhelpforum @mathhelpforum