Results 1 to 7 of 7

Math Help - complicated problem...

  1. #1
    Newbie
    Joined
    Nov 2008
    Posts
    22

    complicated problem...

    Dear all,
    I have a problem that is drive me crazy...
    its description is so simple:
    You have M balls and L holes (M \gtrless L). The balls are indistinguishable and are putted in the holes randomly (following a uniform probability distribution). The holes can take an infinite number of balls each.
    At the end of the assignment every hole can contain 0, 1 or more balls.

    How is it possible to compute the probability to have a certain number of holes with at least one balls in?

    Any suggestion is welcome!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,391
    Thanks
    1476
    Awards
    1
    Before we waste time on a false start, tell us: “Are the M holes distinct”?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Nov 2008
    Posts
    22
    Sorry...
    However, the holes are NOT distinguishable.
    I mean: I want only to know what is the probability that a number of holes are with balls, regardless what holes are.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,391
    Thanks
    1476
    Awards
    1
    Quote Originally Posted by Simo View Post
    The holes are NOT distinguishable.
    In some ways that makes the problem more difficult question.
    It appears that you may be thinking of number of ways to partition an integer.
    For example: to partition 6.
    \begin{array}{lll}<br />
   {1 + 1 + 1 + 1 + 1 + 1} & {4 + 1 + 1} & {5 + 1}  \\<br />
   {2 + 1 + 1 + 1 + 2} & {3 + 2 + 1} & {4 + 2}  \\<br />
   {3 + 1 + 1 + 1} & {2 + 2 + 2} & {3 + 3}  \\<br />
   {2 + 2 + 1 + 1} & {} & 6  \\ \end{array}
    There are 11 ways to partition 6.
    If you had 6 balls and 3 holes the from above there are 3 ways to do it with no hole empty.
    There are several recursive relations involved in partitions an integer.
    Here is a very readable reference: Mathematics of Choice by Ivan Niven.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Nov 2008
    Posts
    22
    Actually, the solution I had posted below is wrong!

    ------------


    something strange:
    looking in a technical paper I've probably find the solution; the problem is that... it is given as a simple formula, without any explanation (probably it is a trivial result ?!?!) and I cannot understand it so much...
    the solution is:
    M balls
    L holes
    probability that i holes have at least one ball
    \Pr (i)=\binom{L}{L-i}\left( \frac{i}{L}\right) ^{M}-\binom{L}{L-i+1}\left( <br />
\frac{i-1}{L}\right) ^{M}
    it seems like the difference of two binomial cumulative distribution functions (hence \Pr (x\leq i)-\Pr (x\leq i-1), considering \Pr (x\leq i) as the probability that the number x of holes that have at leas one balls in is less or equal to i). But, also knowing this hypothesis of solution, I cannot understand how it can be reach from the definition of a binomial distribution.
    Some ideas about it?
    Thanks!
    Last edited by Simo; November 14th 2008 at 08:25 AM. Reason: correction
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Nov 2008
    Posts
    22
    Actually, the information I had posted above is NOT TRUE.
    It works only in with certain constraint on M and L...moreover, i've made some numerical simulations and it seems to be something like an approximation. So, it is useless...the problem is still open!
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1
    Quote Originally Posted by Simo View Post
    Dear all,
    I have a problem that is drive me crazy...
    its description is so simple:
    You have M balls and L holes (M \gtrless L). The balls are indistinguishable and are putted in the holes randomly (following a uniform probability distribution). The holes can take an infinite number of balls each.
    At the end of the assignment every hole can contain 0, 1 or more balls.

    How is it possible to compute the probability to have a certain number of holes with at least one balls in?

    Any suggestion is welcome!
    Hi Simo,

    Allow me to rephrase the problem slightly so that we are finding the probability that there will be k empty holes, where 0 \leq k \leq L.

    Here is a solution using the Generalized Principle of Inclusion and Exclusion (PIE). Given some arrangement of balls in the holes, let’s say the arrangement has property j if hole number j is empty, for 1 \leq j \leq L. Let S_i be the total probability of all the arrangements with i properties, i.e. the probability that i holes will be empty. If i holes are empty then there are \binom{L}{i} ways to choose the empty holes and the probability that all M balls will land in the remaining L-i holes is \left( \frac{L-i}{L} \right) ^M, so

    S_i = \binom{L}{i} \left( \frac{L-i}{L} \right) ^M \qquad (*)

    By the Generalized PIE, the probability of exactly k empty holes, i.e. the probability of an arrangement with exactly k of the “properties”, is

    P(k) = S_k - \binom{k+1}{k}S_{k+1} + \binom{k+2}{k}S_{k+2}- \dots + (-1)^{L-k}\binom{L}{k}S_L,

    Where S_k, S_{k+1}, etc. are given by (*).
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Complicated Combinatorics Problem
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 8th 2010, 02:48 PM
  2. A complicated problem
    Posted in the Algebra Forum
    Replies: 1
    Last Post: August 19th 2009, 04:47 PM
  3. Please help - complicated D=RT problem
    Posted in the Algebra Forum
    Replies: 2
    Last Post: April 23rd 2009, 04:53 AM
  4. Complicated Log problem
    Posted in the Algebra Forum
    Replies: 3
    Last Post: December 18th 2008, 10:44 AM
  5. Complicated Problem!!
    Posted in the Calculus Forum
    Replies: 3
    Last Post: October 11th 2007, 03:15 PM

Search Tags


/mathhelpforum @mathhelpforum