In Problem 7.9, compute the variance of the number of empty urns.

Total Number of balls$=n$numbered through 1

Number of urns $=n$also numbered 1 through $n$

Ball$i$is equally likely to go into any of the urns$1,2,...,i.$

We can write the Number of urns that are empty as,

$\mathrm{X}=\sum _{i=1}^{\mathrm{n}}{\mathrm{X}}_{\mathrm{i}}$

Where

$X_i=\left\{\begin{array}{l}1\hspace{0.25em}\hspace{0.25em}\hspace{0.25em}\hspace{0.25em}\text{if}{i}^{\text{th}}\text{urn is empty}\\ 0\hspace{0.25em}\hspace{0.25em}\hspace{0.25em}\hspace{0.25em}\text{otherwise}\end{array}\right.$

So,

$\mathrm{E}\left[{\mathrm{X}}_{\mathrm{i}}\right]=1\times P\left(X_i=1\right)+0\times P\left(X_i=0\right)$

$=P\left(X_i=1\right)$

$=P\{\text{ball}\mathrm{j}\text{is not in urn}\mathrm{i},\mathrm{j}\ge \mathrm{i}\}$

$=\prod _{\mathrm{j}=i}^{\mathrm{n}}(1-\frac{1}{j})$

Calculate the expected value:

$=P\left(X_i=1\right)$

$=P\{\text{ball}\mathrm{j}\text{is not in urn}\mathrm{i},\mathrm{j}\ge \mathrm{i}\}$

$=\prod _{\mathrm{j}=i}^{\mathrm{n}}\left(1-\frac{1}{j}\right)$

Calculate the variance:

$Var\left({\mathrm{X}}_{\mathrm{i}}\right)=E\left(X_i^2\right)-{\left[E\left(X_i\right)\right]}^2$

$=E\left(X_i\right)-{\left[E\left(X_i\right)\right]}^2$[Since$E\left(X_i^2\right)=E\left(X_i\right)$as seen above]

$=E\left(X_i\right)\left[1-E\left(X_i\right)\right]$

Calculate for$i$

$E\left[X_i{X}_k\right]=1\times 1\times P\left(X_i{X}_k=1\right)$

$=P\left(X_i{X}_k=1\right)$

$=P\left(X_i=1,X_k=1\right)$

$=\prod _{\mathrm{j}-\mathrm{i}}^{\mathrm{k}-1}\left(1-\frac{1}{\mathrm{j}}\right)\prod _{\mathrm{j}-\mathrm{k}}^{\mathrm{n}}\left(1-\frac{2}{\mathrm{j}}\right)$

Hence for $i<k,$

$Cov\left(X_i,X_k\right)=E\left(X_i{X}_k\right)-E\left(X_i\right)E\left(X_k\right)$

$=\prod _{\mathrm{j}=\mathrm{i}}^{\mathrm{k}-1}\left(1-\frac{1}{\mathrm{j}}\right)\prod _{\mathrm{j}=\mathrm{k}}^{\mathrm{n}}\left(1-\frac{2}{\mathrm{j}}\right)-\prod _{\mathrm{j}=i}^{\mathrm{n}}\left(1-\frac{1}{\mathrm{j}}\right)\prod _{\mathrm{j}=\mathrm{k}}^{\mathrm{n}}\left(1-\frac{1}{\mathrm{j}}\right)$

Compute the variance of the number of empty urns,

$=\mathrm{E}\left({\mathrm{X}}_{\mathrm{i}}\right)\left[1-\mathrm{E}\left({\mathrm{X}}_{\mathrm{i}}\right)\right]+2Cov\left(X_i{X}_k\right)$

$=\prod _{\mathrm{j}=i}^{\mathrm{n}}\left(1-\frac{1}{j}\right)\left[1-\prod _{\mathrm{j}=i}^{\mathrm{n}}\left(1-\frac{1}{j}\right)\right]+2\left[\prod _{\mathrm{j}=i}^{\mathrm{k}-1}\left(1-\frac{1}{\mathrm{j}}\right)\prod _{\mathrm{j}=\mathrm{k}}^{\mathrm{n}}\left(1-\frac{2}{\mathrm{j}}\right)-\prod _{\mathrm{j}=i}^{\mathrm{n}}\left(1-\frac{1}{\mathrm{j}}\right)\prod _{\mathrm{j}=\mathrm{k}}^{\mathrm{n}}\left(1-\frac{1}{\mathrm{j}}\right)\right]$

Hence, the variance of the number of empty urns is$=\prod _{\mathrm{j}=i}^{\mathrm{n}}\left(1-\frac{1}{j}\right)\left[1-\prod _{\mathrm{j}=i}^{\mathrm{n}}\left(1-\frac{1}{j}\right)\right]+2\left[\prod _{\mathrm{j}=i}^{\mathrm{k}-1}\left(1-\frac{1}{\mathrm{j}}\right)\prod _{\mathrm{j}=\mathrm{k}}^{\mathrm{n}}\left(1-\frac{2}{\mathrm{j}}\right)-\prod _{\mathrm{j}=i}^{\mathrm{n}}\left(1-\frac{1}{\mathrm{j}}\right)\prod _{\mathrm{j}=\mathrm{k}}^{\mathrm{n}}\left(1-\frac{1}{\mathrm{j}}\right)\right].$