91Ó°ÊÓ

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.

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

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)×\left(1-\frac{1}{i+1}\right)×\left(1-\frac{1}{i+2}\right)×…\left(1-\frac{1}{n}\right)$

Simplify the value,

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

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

Substitute,

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

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

$E\left(X\right)=\underset{i=1}{\overset{n}{∑}}E\left(X_i\right)=\underset{i=1}{\overset{n}{∑}}\frac{i-1}{n}$

$=\frac{1}{n}\underset{i=1}{\overset{n}{∑}}i-1$

$=\frac{1}{n}\underset{j=0}{\overset{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}$.

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

The probability that none of the urns is empty.

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

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

$P=\frac{1}{n}×\frac{1}{n-1}×\frac{1}{n-2}×…\frac{1}{1}$

Simplify,

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

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