2
$\begingroup$

enter image description here

Question: What is the probability that none of the urns is empty?

Try

Notice that the sample space has size $n^n$ as any of the n urns can hold n balls. now in how many ways can we have all the urns ocupied? Well, this is only possible if each ball is in at most one urn, that is we just permute the n balls and so the required probability is

$$ \frac{n!}{n^n} $$

which is wrong as the answer key says $\frac{1}{n!}$. What is my wrongdoing here? I believe my argument is correct.

Perhaps am I misunderstanding the problem? Do we assume that the ith ball can only go to any urn numbered 1 thru $i$ but not after this. So for instance, ball $3$ cannot be placed in urn $5$. is this what they mean ?

$\endgroup$
  • $\begingroup$ Yes, that's exactly what they mean. $\endgroup$ – saulspatz Nov 28 '18 at 22:05
2
$\begingroup$

The first ball has only one choice, i.e. urn 1. This implies that urn 1 will be full with probability 1.

The second ball has two choices: urn 1 and urn 2. With probability $1/2$, the ball will go to urn 2, implying both urn 1 and urn 2 will be full.

You can continue this logic to see that the probability of having a ball in each urn is $1 \times 1/2 \times 1/3 ... = 1/n!$.

$\endgroup$
2
$\begingroup$

Start with $n=1$. One urn one ball probability 1 that the urn is not empty.

Suppose that the premise holds for $n=k$, then the probability that there is no empty urn is the probability that the first $k$ balls are one per urn times the probability that the next ball $(k+1)$ is in the $k+1$th urn, which is $\frac{1}{k+1}$. Thus if the premise holds for $k$ it will hold for $k+1$.

Proved by induction

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.