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.

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 the expected number of urns that are empty.

Can somebody help me? I don´t understand.

Thanks very much.

share|improve this question
1  
Do you mean that ball $i$ is equally likely to into any of the urns $1,2, \dots i$ or $1,2,\dots, n$? That is, is it impossible that, for example, ball 3 goes into urn 4? Or is any ball equally likely to go into any urn? –  sol May 20 '13 at 1:19
    
I think that it must be the latter. 'Cause if Ball #1 can't go in Urn #2 or up, then it goes in Urn #1. Then Ball #2 can't go in Urn #3 or above, and Urn #1 is occupied, so... The whole thing falls apart. –  User58220 May 20 '13 at 2:42
    
If it helps anyone formulate a proof, the expected value of empty urns for $n=1,2,3,4$ is $0,1/2,1,3/2$ respectively. From this, we might expect $(n-1)/2$ empty urns, given $n$. –  A Walker May 20 '13 at 2:57
    
@User58220 It never says that the urns can't hold multiple balls. Thus it may be that "the prior" holds. –  A Walker May 20 '13 at 2:59

2 Answers 2

up vote 3 down vote accepted

Let $X$ be the number of empty urns. Then $X=X_1+X_2+\dots+X_n$ where $X_i$ is the indicator variable whose value is $1$ if the $i$th urn is empty, $0$ otherwise. Then $E(X_i)$ is the probability that the $i$th urn is empty, i.e., $E(X_i)=\frac{i-1}{i}\frac{i}{i+1}\frac{i+1}{i+2}\dots\frac{n-1}{n}=\frac{i-1}{n}$ (telescoping product). By linearity of expectation, $$E(X)=E(X_1)+\dots+E(X_n)=\frac{0}{n}+\frac{1}{n}+\frac{2}{n}+\dots+\frac{n-1}{n}=\frac{{n\choose 2}}{n}=\frac{n-1}{2}.$$

share|improve this answer

We proceed by induction. For the case $n=1$, it is clear that the expected value of empty urns is $0$. Now, suppose that with $n$ urns our expected value, $E(n)$, is given by $(n-1)/2$.

For the case $n+1$, we can think of our procedure in two steps:

  1. Place $n$ balls (according to the rule for $n$ balls) into the first $n$ urns.
  2. Place one ball in any urn.

After step 1, there are on average $E(n)+1$ empty urns. As the last ball will end up in any urn with equal probability, there is a probability of $(E(n)+1)/(n+1)$ that our final ball will land in an empty urn. Subtracting, there remains a $(n-E(n))/(n+1)$ chance that the final ball will land in a previously-occupied urn. That is, our expected value on empty urns is given by

$$E(n+1)=E(n) \left(\frac{E(n)+1}{n+1}\right)+(E(n)+1)\left(\frac{n-E(n)}{n+1}\right)=\frac{n-1}{2}\cdot \frac{1}{2} + \frac{n+1}{2}\cdot \frac{1}{2},$$ in which we've used the inductive hypothesis $E(n)=(n-1)/2$. The right-hand side of the expression above is $n/2$, and this proves the $n+1$ case (so that we conclude by induction).

I'd like to point out that I would not have known how to formulate this induction without doing some cases by hand. I noticed that this pattern held for $n \leq 4$ before attempting the proof you see above.

share|improve this answer
    
@A Walker Thanks you very much ,You helped me a lot :D –  user63192 May 20 '13 at 3:47

Your Answer

 
discard

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.