I have a question with my reasoning (or lack thereof) — I understand what the correct answer is, but I do not see the gap in my logic.
Premise:
We have $n$ balls and we randomly allocate them to $n$ buckets with equal probability. What is the probability that exactly one bucket remains empty?
My Attempt:
Let us start by determining the probability of allocating $n-1$ balls among $n$ buckets such that there is exactly one empty bucket.
As $n\over{n}$ of the buckets are initially empty, the first ball is always placed in an empty bucket (i.e. probability of $n\over{n}$). After placing the first ball, ${n-1}$ of $n$ buckets are empty, so the probability of placing the 2nd ball into an empty bucket is ${n-1}\over n$. This continues on for the $n-1$ balls as follows:
$$\text{P(Exactly One Bucket Empty)}= { n\over n} \times { n-1\over n} \times { n-2\over n} \times … \times { 2\over n} = {n! \over n^{n-1}}$$
Now we can multiply that probability by the probability that we allocate the final ball to one of the $n-1$ buckets that are already occupied. This should yield the probability of allocating $n$ balls among $n$ buckets such that exactly one bucket is empty.
The calculation is as follows:
$$ = {n! \over {n^{n-1}}} \times {{n-1}\over{n}} = {{{n!}\times(n-1)}\over{n^n}} = {{(n-1)! \times (n-1)}\over{n^{n-1}}}$$
Problem with my answer:
Most answers I have seen give the answer as:
$$={{(n-1)! \times (n-1)}\over{2n^{n-2}}}$$
So, I appear to be off by a factor of $n\over 2$. Any suggestions on where I made an error in my logic? Thank you.
Best Answer
The problem with your logic is that you are introducing an extra restriction. You are allowing only the last ball to be paired with another ball. In other words you are forcing the last ball to necessarily be in the bin with $2$ balls. This is a restriction that the question doesn't have.
Here's how we can correct it. What you are doing with the last ball can be done with any of the $n$ balls. So multiply by $n$.
However, putting the $i^{th}$ ball in the bin containing the $j^{th}$ ball is the same as putting the $j^{th}$ ball in the bin containing the $i^{th}$ ball. So we need to divide by $2$.
So the correct answer would be
$$\frac{(n-1)(n-1)!}{n^{n-1}} \times \frac{n}{2} = \frac{(n-1)(n-1)!}{2 n^{n-2}}$$
Response to OP's comment
Let me rephrase your solution from the start. Perhaps it will help you gain an intuitive understanding.
Let's find the probability that $i^{\text{th}}$ ball ends up with the $j^{\text{th}}$ ball (as a pair) in one bin and the other balls go into separate bins. We will label this $P(E_{ij})$
For this, imagine placing each ball into a separate bin one by one, with one caveat. When we get to the $j^{\text{th}}$ ball, we hold on to it and move on to the next ball. at the end we will have placed $n-1$ balls in $n-1$ bins and we will have the $j^{\text{th}}$ ball with us. The probability for this is
$$\frac{n}{n} \cdot \frac{n-1}{n} \cdot \frac{n-2}{n} \cdots \cdot \frac{2}{n} = \frac{n!}{n^{n-1}}$$
Now, the ball still with us ($j^{\text{th}}$) must go into one specific bin - that with the $i^{\text{th}}$ ball. The probability for this happening is $\dfrac{1}{n}$. Multiplying this with the above expression, we get
$$P(E_{ij}) = \frac{n!}{n^{n-1}} \times \frac{1}{n} = \frac{(n-1)!}{n^{n-1}}$$
As you can see $P(E_{ij})$ is a constant independent of $i$ and $j$. Now, to get the total probability for exactly one bin to be empty we need to add it for all pairs of balls. Or multiply it with the number of pairs possible, $\dfrac{n (n-1)}{2}$. So
$$\begin{align*} P &= \frac{(n-1)!}{n^{n-1}} \times \frac{n (n-1)}{2} \\[0.3cm] &= \frac{(n-1)(n-1)!}{2n^{n-2}} \end{align*}$$