Before we waste time on a false start, tell us: “Are the M holes distinct”?
Dear all,
I have a problem that is drive me crazy...
its description is so simple:
You have balls and holes . 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!
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.
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.
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:
balls
holes
probability that i holes have at least one ball
it seems like the difference of two binomial cumulative distribution functions (hence , considering as the probability that the number of holes that have at leas one balls in is less or equal to ). 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!
Actually, the information I had posted above is NOT TRUE.
It works only in with certain constraint on and ...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!
Hi Simo,
Allow me to rephrase the problem slightly so that we are finding the probability that there will be empty holes, where .
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 if hole number is empty, for . Let be the total probability of all the arrangements with properties, i.e. the probability that holes will be empty. If holes are empty then there are ways to choose the empty holes and the probability that all balls will land in the remaining holes is , so
By the Generalized PIE, the probability of exactly empty holes, i.e. the probability of an arrangement with exactly of the “properties”, is
,
Where , , etc. are given by (*).