Q.7.32 - A First Course in Probability

Question

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

Step-by-Step Solution

Answer

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}=\mathrm{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].$

Step 1: Given Information

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

Step 2: write the Number of urns

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

Step 3: Calculate the expected value and variance

Calculate the expected value:

$E\left(X_i^2\right)=1^2\times P\left(X_i=1\right)+0^2\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}}\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]$

Step 4: Calculate for i   a n d   i < k

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

Step 5: Compute the variance of the number

Compute the variance of the number of empty urns,

$Var\left(X\right)=\sum _{i=1}^{n}Var\left(X_i\right)+2Cov\left(X_i{X}_k\right)$

$=\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]$

Step 6: Final Answer

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