I am not able to figure out a loophole in my argument related to popular "Balls into bins" problem.
Suppose there are $m$ balls and $n$ bins. The $m$ balls are thrown independently and uniformly at random into these $n$ bins. What is the probability that the first bin is empty ?
The answer to this question mentioned in : Probability that first ball is empty
is $\Big(1-\frac{1}{n}\Big)^m$ which seems fine.
This answer should match with the probability found using manual counting method.
My argument is:
The $m$ balls can be distributed into $n$ bins in ${m+n-1} \choose {n-1} $ ways. If first bin is empty, then $m$ balls can be distributed into remaining $(n-1)$ bins in ${m+n-2} \choose {n-2} $ ways. This implies,
$$P(\text{first bin is empty})=\frac{{m+n-2} \choose {n-2}}{ {m+n-1} \choose {n-1} }=\frac{n-1}{m+n-1}$$
The values of both probabilities are very close to each other but have different answers. What is wrong with my argument ?
Best Answer
If you want a counting argument then each case must be equally likely.
Your ${m+n-1 \choose n-1}$ ways of distributing $m$ balls into $n$ bins are not equally likely. There are $n^m$ equally likely ways of distributing the balls but some look similar to each other.
Take a simple example of $m=3,n=2$. Then ${m+n-1 \choose n-1}= {4 \choose 1}=4$ wheile $n^m = 2^3=8$. The different ways are:
This last case is leaves the first bin empty and has probability $\frac18 = \left(1-\frac12\right)^3$.