Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Would love if someone could help me double-check my work. Thanks a lot!

A total of n balls, numbered $1$ through $n$, are put into $n$ urns, also numbered $1$ through $n$ in such a way that, for each $i = 1, 2,...,n$, ball $i$ is equally likely to go into any of the urns, $1, 2,..., i$. It is further assumed the balls are put into the urns independently.
Introduce the following indicator random variables: for $k = 1, 2,..., n$,
${I_k} = \left\{ {\begin{array}{*{20}{c}} {1,} & \text{ if kth urn is empty} \\ {0,} & \text{ otherwise} \\ \end{array}} \right.$

(i) Find the expected number of urns that are empty.
(ii) In this and the next parts, let $n = 4$. For $2 \le j < k \le 4$, evaluate the probability ${\rm P}\{ {I_j} = 1,{I_k} = 1\} $.
(iii) Calculate the variance of the number of urns that are empty.

(i) When we put the first $(k-1)$ balls into the urns, the $k\text{th}$ urn remains empty. The probability that $k\text{th}$ urn remains empty after the $k\text{th}$ drop is $1 - \frac{1}{k}$, after the $(k+1)\text{st}$ drop is $1 - \frac{1}{{k + 1}}$, etc. Thus, ${\rm E}[{I_k}] = P\{ {I_k} = 1\} = \left( {1 - \frac{1}{k}} \right)\left( {1 - \frac{1}{{k + 1}}} \right)...\left( {1 - \frac{1}{n}} \right) = \frac{{k - 1}}{n}$, and ${\rm E}[I] = {\rm E}[\sum\limits_{k = 1}^n {{I_k}} ] = \sum\limits_{k = 1}^n {{\rm E}[{I_k}]} = \sum\limits_{k = 1}^n {\frac{{k - 1}}{n}} = \frac{1}{n}\sum\limits_{k = 0}^{n - 1} k = \frac{{n - 1}}{2}$

(ii) We first calculate the conditional probabilities, for example $P\{ {I_3} = 1|{I_4} = 1\} $. In the first 2 drops, the third urn is empty. The third urn remains empty after the third drop with probability $2/3$, and after the fourth drop with the same probability $2/3$, since it's given that the fourth urn is empty. Therefore, ${\rm P}\{ {I_3} = 1|{I_4} = 1\} = \frac{2}{3} \times \frac{2}{3} = \frac{4}{9}$. By the same reasoning, ${\rm P}\{ {I_2} = 1|{I_4} = 1\} = \frac{1}{2} \times \frac{2}{3} \times \frac{2}{3} = \frac{2}{9}$,${\rm P}\{ {I_2} = 1|{I_3} = 1\} = \frac{1}{2} \times \frac{1}{2} \times \frac{2}{3} = \frac{1}{6}$. Hence, ${\rm P}\{ {I_j} = 1,{I_k} = 1\} = \sum\limits_{2 \le j < k \le 4} {{\rm P}\{ {I_j} = 1|{I_k} = 1\} {\rm P}\{ {I_k} = 1\} } = \frac{4}{9} \times \frac{3}{4} + \frac{2}{9} \times \frac{3}{4} + \frac{1}{6} \times \frac{2}{4} = \frac{1}{3} + \frac{1}{6} + \frac{1}{{12}} = \frac{7}{{12}}$

(iii) ${\rm Cov}({I_3},{I_4}) = {\rm E}[{I_3}{I_4}] - {\rm E}[{I_3}]{\rm E}[{I_4}] = P\{ {I_3} = 1,{I_4} = 1\} - P\{ {I_3} = 1\} P\{ {I_4} = 1\} = \frac{1}{3} - \frac{2}{4} \times \frac{3}{4} = - \frac{1}{{24}}$ Similarly, ${\rm Cov}({I_2},{I_4}) = \frac{1}{6} - \frac{1}{4} \times \frac{3}{4} = - \frac{1}{{48}}$,${\rm Cov}({I_2},{I_3}) = \frac{1}{{12}} - \frac{1}{4} \times \frac{2}{4} = - \frac{1}{{24}}$

$\begin{array}{l} {\rm E}[{I_k}^2] = P\{ {I_k}^2 = 1\} = P\{ {I_k} = 1\} = \frac{{k - 1}}{4} \\ {\rm Var}({I_k}) = {\rm E}[{I_k}^2] - E{[{I_k}]^2} = \frac{{k - 1}}{4} - {\left( {\frac{{k - 1}}{4}} \right)^2} \\ \end{array}$ ${\rm Var}(I) = {\rm Var}(\sum\limits_{k = 2}^4 {{I_k})} + 2{\sum {\sum\limits_{2 \le j < k \le 4} {{\rm Cov}({I_j},{I_k}) = \sum\limits_{k = 2}^4 {\frac{{k - 1}}{4} - \left( {\frac{{k - 1}}{4}} \right)} } } ^2} + 2{\rm Cov}({I_3},{I_4}) + 2{\rm Cov}({I_2},{I_4}) + 2{\rm Cov}({I_2},{I_3}) = \frac{5}{8} - 2 \times \left( {\frac{1}{{24}} + \frac{1}{{48}} + \frac{1}{{24}}} \right) = \frac{5}{{12}}$

share|improve this question
1  
Your answers seem correct (I've checked most but not all of your steps). The index variables don't look meaningful/correct in your last sentence for part (ii): you begin with a probability depending on a particular $i$ and $j$, and then have a summation over $j$ and $k$ conditioning on $j$. Also, you left out the factor of $2$ in the covariances in the last step in which they appear in part (iii). Otherwise (apart from these typos), it looks correct. –  bgins Apr 14 '13 at 6:21
    
Edited. Thanks for spotting them out! –  drawar Apr 14 '13 at 6:35
    
My understanding is that you are being asked for $P\{I_j=1,I_k=1\}$ for $2\le j<k\le 4$, i.e. for $3$ tuples $(j,k)$, namely $(2,3)$, $(2,4)$ and $(3,4)$. When you introduce the summation, however, you seem to be summing the probabilities of each of these possibilities. However, that does not seem to be what you were asked. –  bgins Apr 14 '13 at 6:41
    
I thought $P{I_{j}=1,I_{k}=1}$ was the union of the three probabilities so I just added them up. Is it wrong? –  drawar Apr 14 '13 at 7:17
    
It's a joint probability, which we can think of as the intersection of each separate event. If we can condition on some other variable (or event) over three mutually exclusive cases, then we could also represent this as the sum of probabilities in those cases. –  bgins Apr 14 '13 at 16:42

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.