We have $n$ bins and $k$ balls, with $1 \leq k \leq n$.
The balls are placed in the bins, knowing that the placement of each ball is independent of the others, and that the bins are chosen in an equiprobable way.
- Calculate the probability that each bin contains at most one ball.
- Calculate the probability that a bin contains all balls.
- Calculate the probability that a bin contains at least two balls.
My attempt:
- The probability that each bin contains at most one ball is the probability that a bin contains at most one ball $n$ times. Now, the probability that a bin contains at most one ball is the probability that it contains exactly one ball plus the probability that it contains no balls.
I think that the probability that it contains exactly one ball is $k/n$.
I cannot continue. Any helps? Thanks.
Best Answer
Assuming you have 1., you can immediately get 3.: these are complementary events.
To answer 1., observe that for this even to happen, you first need to place the first ball into any bin; then the second into any of the remaining $n-1$ bins; then the third into any of the remaining $n-2$ bins; etc. So your probability is $$ \mathbb{P}\{\text{no collision}\} = 1\cdot\frac{n-1}{n}\cdot\frac{n-2}{n}\cdots\cdot\frac{n-(k-1)}{n} = \prod_{\ell=0}^{k-1} \frac{n-\ell}{n} = \frac{n!}{n^k (n-k)!} $$ Sanity check: for $k=1$, you get $1$.
Now, to answer 2. Your event corresponds to the union of $n$ disjoint events (namely: "all balls in bin #1", "all bins in bin #2", ..., "all balls in bin #n"). The probability of each of these events is exactly $$ \left(\frac{1}{n}\right)^k = \frac{1}{n^k} $$ since the $k$ balls are placed independently. So the overall probability is $n\cdot \frac{1}{n^k} = \frac{1}{n^{k-1}}$. (again, for $k=1$, you do get $1$, as expected).