# Different approaches to N balls and m boxes problem

Suppose that you have N indistinguishable balls that are to be distributed in m boxes (the boxes are numbered from 1 to m). What is the probability of the i-th box being empty (where the i-th box is the box with the number i) given that the balls have equal chances of arriving at any box?

I found two different approaches to solve this problem (which I post bellow). Since each of them leads to a different solution, I am having a hard time trying to find which one is incorrect. I am fairly sure that the first approach is correct since it follows the 'standard' way of solving problems involving indistinguishable balls, but I cannot find the error in the second one. I would greatly appreciate any help you could provide to solve this doubt.

(1) First approach: (Bosons) The number of ways of distributing N indistinguishable balls into m boxes is equal to: $$\binom{N + m -1}{N}=\frac{(N + m - 1)!}{N!(m-1)!}$$ On the other hand, the number of ways to distribute the balls and leaving the i-th box empty can be obtained by leaving the i-th box empty and distributing the N balls into the remaining m - 1 boxes. This is equal to: $$\binom{N + m - 2}{N}=\frac{(N + m - 2)!}{N!(m-2)!}$$ Therefore the probability of the i-th box being empty is the quotient of the second number by the first: $$\frac{(N + m - 2)!}{N!(m-2)!}.\frac{N!(m-1)!}{(N + m - 1)!}=\frac{m-1}{N + m - 1}$$ (2) Second approach: (Counting functions) Suppose that before distributing the balls into the boxes we number them from 1 to N. Then for each ball, the number of ways of distributing that ball into the m boxes is m. So the number of ways to distribute N balls into m boxes is: $$m^N$$ If we want to distribute N numbered balls into m boxes leaving the i-th box empty, each ball can only go to the m-1 remaining boxes. Therefore the number of ways in which this can be done is: $$(m-1)^N$$ And the desired probability will be the quotient: $$\left(\frac{m-1}{m}\right)^N \neq \frac{m-1}{N + m - 1}$$

Thank you very much for your time.

• I had a doubt, I followed all the discussion below, and instead writing this out as an answer, I am commenting here.. As I understand, the fact that the balls are indistinguishable bears no effect on the solution, it is as good as considering them to be distinguishable, BECAUSE, we count the number of ways the balls "arrive" (to the urns) and not the final configurations themselves. As a side note, such problems always are so deceptively hard, because probability seems to depend heavily on the semantics (what the words and phrases mean). Any advice for the future? – Vigneshwaren Oct 30 '14 at 16:22

Note: The formulation of this question has to be considered carefully in order to find the correct approach.

The situation describes $N$ indistinguishable balls which are to be distributed in $m$ distinguishable boxes.

Looking at a simple example as suggested by @MickA is often a good starting point. Let's have a look at an example with $N=2$ indistinguishable balls and $m=2$ distinguishable boxes. So, after distributing the $2$ balls into the $2$ boxes, we can see one of three possible outcomes:

\begin{array}{rcl} \text{Box $1$} &|& \text{Box $2$} \\ \hline \bullet\;\bullet &|& \\ \bullet &|& \bullet \\ &|&\bullet\; \bullet \end{array}

We observe, if the question would have asked for something like

• number of possible outcomes or

• number of different configurations

The Ansatz would be according to the first approach

\begin{align*} \binom{N+m-1}{N}\tag{1} \end{align*}

which respects the fact that the balls are indistinquishable and the boxes are distinguishable.

But this is not the question! The crucial text is:

... given that the balls have equal chances of arriving at any box.

Therefore we have to count the number of possible arrivals

\begin{array}{rclcc} \text{Box $1$} &|& \text{Box $2$} &|& \text{Nr of possibilities}\\ &|& &|& \text{to reach this configuration}\\ \hline \bullet\;\bullet &|& &|& 1\\ \bullet &|& \bullet &|& 2\\ &|&\bullet\; \bullet&|& 1 \end{array}

We see, counting the number of possibilities or equivalently calculating the corresponding probabilities

\begin{array}{rclcc} \text{Box $1$} &|& \text{Box $2$} &|& \text{probability}\\ &|& &|& \text{to reach this configuration}\\ \hline \bullet\;\bullet &|& &|& 0.25\\ \bullet &|& \bullet&|& 0.50\\ &|&\bullet\; \bullet&|& 0.25 \end{array}

is a different situation than (1) leading to the second approach

$$m^N$$

Result:

Therefore, we finally get the probability:

$$\left(\frac{m-1}{m}\right)^N$$

• Thanks a lot for granting the bounty and accepting the answer! :-) Best regards, – Markus Scheuer Oct 31 '14 at 19:40

In the second approach you don't impose indistinguishability. The second approach is correct in the usual practical settings. Even if we don't consider the balls to be distinguishable, they are in principle physically distinguishable.

In the first approach where the balls are really indistinguishable, you are effectively assuming that the identical balls are in a quantum state that has equal amplitudes for all the possible number states. Compared to the second case, you get a larger probability for the balls ending up in the same box, which is to be expected for bosons.

You should use approach $2$ for this problem. The difference in the two approaches is in the probability of getting a given number of balls in a given box. If the probabilities of getting $0,1,2,\ldots$ balls in a given box are the same/uniform then use approach $1$. For this particular problem that's not true.

Take a simple example of your problem with $N=2$ balls (numbered $1,2$) and $m=2$ boxes. The possible outcomes, all equally likely, are:

\begin{eqnarray*} \text{Box $1$} &|& \text{Box $2$} \\ \hline 1\; 2 &|& \\ 1 &|& 2 \\ 2 &|& 1 \\ &|& 1\; 2 \end{eqnarray*}

The following probabilities, being unequal, mean approach $1$ fails:

\begin{eqnarray*} P(\text{Box $1$ has $0$ balls}) = \dfrac{1}{4} \\ P(\text{Box $1$ has $1$ ball}) = \dfrac{1}{2} \\ P(\text{Box $1$ has $2$ balls}) = \dfrac{1}{4} \end{eqnarray*}

Approach $1$ (commonly called "stars and bars") is often used for counting problems that don't involve probabilities, such as those of the form "Find the number of solutions to $x_1 + x_2 + x_3 = 10$ with $x_1,x_2,x_3$ non-negative integers".

Count Iblis is right, but one comment: in mathematics and probability theory you do not need to care about quantum physics and Bosons. The answer to which computation is correct depends on how you define the probability space (i.e. by explicitly stating what is your set of configurations and what are their probabilities). Depending on which configurations you treat as equal, you get probability spaces corresponding to each of your solutions.

While the first result seems correct, here is another approach that corroborates the validity of the second result.

The number $X$ of balls in the $i$-th box is a binomial random variable with parameters $p=\dfrac{1}{m}$ and $n=N$. (The process can be thought equivalently as that of a basketball player who is going to throw $N$ free throws and is trying to hit a target with probability $1/m$. Due to the independence between different "throws" the binomial distribution is the appropriate distribution to describe the process probabilistically.)

The required probability is $$P(X=0)=\dbinom{N}{0}\left(\dfrac{1}{m}\right)^0\left(1-\dfrac{1}{m}\right)^{N-0}=\left(\dfrac{m-1}{m}\right)^N$$

Edit1: The problem with the first approach is that it falsely assumes that all the outcomes are equiprobable. Admittedly there are $$\binom{N+m-1}{N}=\dfrac{(N+m-1)!}{N!(m-1)!}$$ ways to distribute $N$ indistinguishable balls in $m$ boxes, but each way does not occur with the same probability.

For example, one way is that all $N$ balls land in one box. Then the distribution looks like $$(N,0,0,\ldots,0)$$ and there $m$ ways that this distribution will occur, one for each box. Now assume for simplicity that $N=2m$ and consider the distribution, where the same number of balls lands in each box. This distribution looks like $$(2, 2, 2, \ldots, 2)$$ but there is now only $1$ way that this distribution will occur! This aspect is not taken in account in the first approach and therefore it yields a wrong result.

Just another -hopefully simpler- example. Suppose we have two balls, $A,B$ (let's assume them distinguishable to begin with) to be placed into two boxes $1,2$. We call "success" the event that both boxes are non empty.

We have four possible configurations:

$$\begin{array}{cc} 1 & 2\\ \hline \{ A,B\} & \emptyset \\ \emptyset &\{ A,B\} \\ \{ A\} & \{ B\}\\ \{ B\} & \{ A\} \\ \end{array}$$

If the balls are placed on each box with the same probability, each configuration have probability $1/4$, hence the probability of success (last two configurations) is $1/4+1/4=1/2$.

Suppose now we are told that the balls are indistinguishable. Then, the last two configurations are actually one, so the number of distinct configurations reduces to three. But, does this change the probability?

The answer depends on the assumed probability model. If the balls are thrown on each ball with equal probability, then it does not change anything. True, we now have only one successful configuration, but it has probability $1/2$ (it can happen in two ways). This should be intuitively obvious: if the probability model has not changed, and if the event of interest does not depend on the balls being distinguishable, the probability should not change.

Instead, if the probability model dictates that the (distinguishable) configurations are equiprobable (as in your Boson model), then the probability of success is $1/3$.