2
$\begingroup$

Suppose we have $n$ balls that are randomly distributed into $N$ boxes. Find the probability that $m$ balls will fall into the first box. Assume that all $N^m$ arrangements are equally likely.

Attempt:

First, we notice that for the first box, we have $n$ choices, and for the second box we also have $n$ choices, and so on. Thus, we have $n^N$ ways to place the balls into the boxes. Pick $m$ balls out of the total $n$ balls, that gives ${n \choose m}$. In how many ways can these $m$ balls go into the first box? Well, in just ${1 \choose 1 }= 1 $ ways. Thus,

$$ P = \frac{ {n \choose m } }{n^N } $$

Is this correct?

$\endgroup$
  • $\begingroup$ Yes!, in first like i assume you mean "we notice that for the first ball" $\endgroup$ – kayush Apr 16 '18 at 1:41
1
$\begingroup$

The number of ways to choose the $m$ items in the first box is $\binom{n}{m}$ and the number of ways to put the remaining $n-m$ items into the remaining $N-1$ boxes is $(N-1)^{n-m}$; therefore, the number of ways to put $m$ items into the first box is $$ \binom{n}{m}(N-1)^{n-m} $$ So the probability is $$ \frac{\binom{n}{m}(N-1)^{n-m}}{N^n}=\frac{\binom{n}{m}}{N^m}\left(1-\frac1N\right)^{n-m} $$ Note that the Binomial Theorem guarantees that $$ \begin{align} \sum_{m=0}^n\binom{n}{m}(N-1)^{n-m} &=((N-1)+1)^n\\ &=N^n \end{align} $$

$\endgroup$
  • $\begingroup$ why $N^n$ on the denominator. Isnt it the size of the sample size $n^N$? There are $1,2,3,...,N$ boxes. In the first box we can put $n$ balls, and in the second box we can put also the n balls and the same for the third, fourth, all the way to the $N$ box. So we have $n\times n \times .. \times n = n^N $ $\endgroup$ – James Apr 16 '18 at 2:41
  • $\begingroup$ To count the number of ways to put $n$ items into $N$ boxes, the first item has the choice of $N$ boxes, the second item has the choice of $N$ boxes, ..., the $n^\text{th}$ item has the choice of $N$ boxes. That is $\underbrace{N\cdot N\cdots N}_{n\text{ items}}=N^n$. $\endgroup$ – robjohn Apr 16 '18 at 3:02
  • $\begingroup$ I dont understand how this is possible? Why can we not just put all the balls in each box ? Im very confused $\endgroup$ – James Apr 16 '18 at 3:04
  • $\begingroup$ For each possible arrangement of the balls in the boxes, each ball can only be in one box. That is, ball $1$ is in one of the $N$ boxes; ball $2$ is in one of the $N$ boxes; ... ball $n$ is in one of the $N$ boxes. A box can contain multiple balls; a ball cannot be in multiple boxes. $\endgroup$ – robjohn Apr 16 '18 at 3:53
  • $\begingroup$ $n=1,N=3:\bbox[5px,border:2px solid black]{o|\phantom{o}|\phantom{o}}\ \bbox[5px,border:2px solid black]{\phantom{o}|o|\phantom{o}}\ \bbox[5px,border:2px solid black]{\phantom{o}|\phantom{o}|o}$. This is $N^n=3^1$ outcomes, not $n^N=1^3$. $\endgroup$ – robjohn Apr 16 '18 at 10:31
0
$\begingroup$

If $X$ is the number of balls that fall into the first box, then $P(X=m)$ follows the binomial distribution, where $p=1/N$.

$\endgroup$
0
$\begingroup$

If we're just concerned with the first box and all other boxes are equally likely, it's just a binomial with $n$ trials, $p=1/N.

$Pr(m=k)={n \choose k}\,p^{k}(1-p)^{n-k}={n \choose k}\,N^{-k}(1-1/N)^{n-k}$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.