Q. 7.9 - A First Course in Probability

Question

A total of n balls, numbered $1$ through n, are put into n urns, also numbered $1$ through $n$ in such a way that ball $i$ is equally likely to go into any of the urns $1,2,..i$ .

Find (a) the expected number of urns that are empty.

(b) the probability that none of the urns is empty. 

Step-by-Step Solution

Answer

a. The expected number of urns that are empty value are $E\left(X\right)=\frac{n-1}{2}$.

b.  The probability that none of the urns is empty value are$\frac{1}{n!}$.

Step 1: Given Information (Part a)

A total of n balls, numbered $1$ through $n,$ are put into $n$ urns, also numbered $1$ through $n$ in such a way that ball $i$ is equally likely to go into any of the urns $1,2,...i$ . 

a. The expected number of urns that are empty.

Step 2: Explanation (Part a)

Let random variable$X$ represent empty urns.

$\left\{\begin{array}{ll}{X}_i=1& \text{ if urn }i\text{ is empty }\\ X_i=0& \text{ otherwise }\end{array}\right\}$

Let us find the expected number of urns that are empty.

For $i^{th}$urn to remain empty, it has to remain empty on$i^{th}$ turn.

In first $i-1$ turn, it will be empty.

Probability that $i^{th}$ ball does not go to $i^{th}$ urn is $\left(1-\frac{1}{i}\right)$.

Step 3: Explanation (Part a)

The probability that the $i+1^{st}$ ball will not land in the urn $i$ is $\left(1-\frac{1}{i+1}\right)$

$E\left(X_i\right)=\left(1-\frac{1}{i}\right)\times \left(1-\frac{1}{i+1}\right)\times \left(1-\frac{1}{i+2}\right)\times \dots \left(1-\frac{1}{n}\right)$

Simplify the value,

$=\left(\frac{i-1}{i}\right)\times \left(\frac{i+1-1}{i+1}\right)·\dots ·\left(\frac{n-1}{n}\right)$

$=\left(\frac{i-1}{i}\right)\times \left(\frac{i}{i+1}\right)\times \left(\frac{i+1}{i+2}\right)\times ... \left(\frac{n-1}{n}\right)$

Substitute,

$=\left(\frac{i-1}{n}\right)$.

Step 4: Explanation (Part a)

Therefore, the expected number of urns that are empty is,

$E\left(X\right)=\sum _{i=1}^{n}E\left(X_i\right)=\sum _{i=1}^n\frac{i-1}{n}$

$=\frac{1}{n}\sum _{i=1}^{n}i-1$

$=\frac{1}{n}\sum _{j=0}^{n-1}j$

Substitute the value,

$\frac{1}{n}\left(\frac{n(n-1)}{2}\right)=\frac{n(n-1)}{2n}$

$=\frac{n-1}{2}$.

Step 5: Final answer (Part a)

The expected number of urns that are empty value are $E\left(X\right)=\frac{n-1}{2}$.

Step 6: Given Information (Part b)

The probability that none of the urns is empty.  

Step 7: Explanation (Part b)

Let us calculate the probability that none of the urns is empty.

For urns not to be empty, the$n^{th}$ ball must be dropped into $n^{th}$ urn.

The probability is $\frac{1}{n}$,

Similarly, 

$n-1^{st}$ ball should go to $n-1^{st}$ urn, the probability is$\frac{1}{n}$.

Step 8: Explanation (Part b)

Therefore, the probability that none of the urns is empty is,

$P=\frac{1}{n}\times \frac{1}{n-1}\times \frac{1}{n-2}\times \dots \frac{1}{1}$

Simplify,

$=\frac{1}{n!}$.

Step 9: Final answer (Part b)

The probability that none of the urns is empty value are $\frac{1}{n!}$.