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.

Short 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-by-step solution

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.

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)$.

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)$.

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}$.

Final answer (Part a)

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

Given Information (Part b)

The probability that none of the urns is empty.

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}$.

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!}$.

Final answer (Part b)

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