6
$\begingroup$

I'm doing a self-review of probability and working through Ross' Introduction to Probability.

The question is (Ross, ch2 number 51): suppose $n$ balls are randomly distributed into $N$ compartments. Find the probability that $m$ balls fall in the first compartment, assuming all $N^n$ arrangements are equally likely.

I solved this two ways -- it's $$\frac{ \displaystyle{n \choose m} (N-1)^{n-m}}{ N^n }.$$ Easy enough. You can also think of this as a bernoulli trial w/ prob $$p = \frac{1}{N}$$ so that $$P(k=m) = \displaystyle{n \choose m} p^m (1-p)^{n-m} = \displaystyle{ n \choose m } \frac{1}{N}^m \left(\frac{N-1}{N}\right)^{n-m}$$ and those are equal. So my answer is probably right.

My question is Ross also mentions a formula for the number of nonnegative integer solutions to $$x_1 + x_2 + \ldots + x_r = n;$$ there are $$\displaystyle{n+r-1 \choose r-1}$$ solutions. So I feel like the answer to this problem should also be the number of solutions to $$x_2 + \ldots + x_N = n - m$$ divided by the number of solutions to $$x_1 + \ldots + x_N = n,$$ ie $$ \frac{\displaystyle{ n - m + (N-1) - 1 \choose (N-1) - 1}}{\displaystyle{n + N - 1 \choose N - 1}} = \frac{\displaystyle{ n - m + N-2 \choose N-2}}{\displaystyle{n + N - 1 \choose N - 1}} $$ but it's not -- I couldn't make this factory correctly, so I tried it with a random choice of numbers for $n,N,m$ and it's definitely not equal. My question is why not? There should be a correspondence between balls in compartments and the number of nonnegative vectors $x_1 + \ldots + x_N = n$, right?

$\endgroup$
0

3 Answers 3

6
$\begingroup$

These are 2 different models of what is meant by equally likely. You cannot mix them.

First consider throwing $r$ balls into $n$ cells. The cells are marked $1,...,n.$ There are $n$ choices for the placement of the first ball, etc., so $n^r$ distinguishable results overall. Each such vector is assigned equal probability $n^{-r}$ as a model of randomness.

The result is the number of balls in each cell: $r_1+r_2+...+r_n=r.$ If we are only interested in this result and the balls are now considered indistinguishable, we need to count the number of distinguishable results that correspond to a given $(r_1,...,r_n).$ That is given by the multinomial coefficient: $$\frac{r!}{r_1!...,r_n!} $$

Note that we are not counting all solutions of $r_1+...+r_n=r.$ Instead, each vector corresponds to creating $n$ subsets of sizes $r_1,...,r_n$ of a set of $r$ items.

Now divide that by $n^r$ to obtain the probability of the vector $(r_1,...,r_n).$

In the second model, also consider $r$ balls and $n$ numbered cells. Again the result is $r_1+...+r_n=r.$ We consider all possible non-negative integer solutions. There are ${ r+n-1 \choose n-1}$ such solutions which we take as equally likely.

An example will make this clear. We throw two dice: $n=6, r=2.$ In the first model there are $n^2=36$ possible results. But now suppose we want the probability of a $5$ and $6$ in either order so $r_5=1, r_6=1$ and the rest are $0$. This probability is $$ \frac {2!}{0!0!0!0!1!1!}\frac{1}{36}=\frac2 {36}. $$ And also, the probability of a double $4$ is $1/36.$

In the second model, we have ${7 \choose 5}=21$ equally likely outcomes. In this model there are $6$ doubles are $15$ non-doubles assumed to have probability $1/21$ each. (Which does not correspond to our world.) In the first model we had $6$ doubles and $30$ non-doubles each with probability $1/36.$ No amount of renormalizing will convert the second model into the first model. Model 1 (called Maxwell-Boltzmann in physics) is what we normally understand as a model of randomness while Model 2 (called Bose-Einstein in physics) is a bit unusual.

$\endgroup$
1
$\begingroup$

Taking N=3, n=5, m=2 we see that using $x_{2}+x_{3}=5-2=3$ method it counts the number of solutions so for example $x_{2}=2$ and $x_{3}=1$ is a solution. but I think problem is that this is saying there is only one combination that can get two balls in 2nd container($x_{2}$) and one ball in 3rd container ($x_{3}$) but this isn't true. You can Label balls A,B,C,D,E and we have $\{(A,B),(C)\},\{(B,C),(A)\},...$ and so on as possible combos that will have solution $x_{2}=2$ and $x_{3}=1$ so though you are counting how many different number of balls you can have in each container 2 and 3 to get three balls total, you aren't counting the number of combinations for each solution. Using this method says any solution is just as likely as the other which is not true.

$\endgroup$
0
$\begingroup$

If we put m identical balls in the first distinct recipient, we will have n-m identical balls in the others N-1 distinct recipients.

Now we use the following proposition:

enter image description here

Thus the number of arrangements that have m identical balls in the first distinct recipient is C(n-m + N-2, N-2).

As the problem requires that we assume that are N^m total arrangements,

the probability is C(n-m + N-2, N-2)/N^m

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .