complicated problem...

**Simo** · November 12th 2008, 12:38 AM

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!

**Plato** · November 12th 2008, 02:53 AM

Before we waste time on a false start, tell us: “Are the M holes distinct”?

**Simo** · November 12th 2008, 03:02 AM

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.

**Plato** · November 12th 2008, 06:52 AM

Originally Posted by Simo

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} {1 + 1 + 1 + 1 + 1 + 1} & {4 + 1 + 1} & {5 + 1} \\ {2 + 1 + 1 + 1 + 2} & {3 + 2 + 1} & {4 + 2} \\ {3 + 1 + 1 + 1} & {2 + 2 + 2} & {3 + 3} \\ {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.

**Simo** · November 13th 2008, 12:29 AM

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( \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!

**Simo** · November 14th 2008, 08:26 AM

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!

**awkward** · November 18th 2008, 07:11 PM

Originally Posted by Simo

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 (*).

Thread: complicated problem...

LinkBack

Thread Tools

Display

complicated problem...

Similar Math Help Forum Discussions

Complicated Combinatorics Problem

A complicated problem

Please help - complicated D=RT problem

Complicated Log problem

Complicated Problem!!

Search Tags