Different approaches to N balls and m boxes problem

Solution 1:

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$$

Solution 2:

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.

Solution 3:

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".

Solution 4:

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.